math - 任意精度算术说明

Question

我正在尝试学习C，并且遇到了无法处理非常大的数字（即100位数字，1000位数字等）的问题。我知道有可以执行此操作的库，但是我想尝试自己实现。

我只想知道是否有人可以或可以提供关于任意精度算术的非常详细，愚蠢的解释。

Answer 1

足够的存储空间和算法可以将数字视为较小的部分。假设您有一个int只能是0到99的编译器，并且您想处理的数字最大为999999（为简化起见，我们只担心正数）。

您可以通过给每个数字三个int并使用您在小学应该（应该）学到的相同规则进行加，减和其他基本操作来做到这一点。

在一个任意精度的库中，用于表示我们的数字的基本类型的数量没有固定的限制，无论内存可以容纳多少。

例如：123456 + 78：

12 34 56
      78
-- -- --
12 35 34

从最低端开始工作：


初始进位= 0。
56 + 78 + 0进位= 134 = 34（1进位）
34 + 00 + 1进位= 35 = 35 0进位
12 + 00 + 0进位= 12 = 12（0进位）


实际上，这就是加法通常在CPU内部的位级别上的工作方式。

减法是相似的（使用基本类型的减法并借位而不是进位），可以通过重复加法（非常慢）或叉积（更快）来进行乘法，除法比较棘手，但是可以通过对数字进行移位和减法来完成参与（您从小就学到的漫长的分裂）。

我实际上已经编写了库来使用最大的10的幂来执行此类操作，平方的平方可以将其乘以整数（以防止在将两个 int乘在一起时发生溢出，例如将16位的 int限制为0到99以生成平方时的9,801（<32,768），或者使用0到9,999生成99,980,001（<2,147,483,648）的32位 int大大简化了算法。

注意一些技巧。

1 /当数字相加或相乘时，请预先分配所需的最大空间，然后在发现过多空间时减少。例如，添加两个100-“数字”（其中数字是 int）数字永远不会给您超过101个数字。将12位数字乘以3位数字将永远不会产生超过15位的数字（加上数字计数）。

2 /为了提高速度，仅在绝对必要时才对数字进行归一化（减少所需的存储空间）-我的库将其作为单独的调用进行调用，以便用户可以在速度和存储空间之间做出选择。

3 /正负数的加法为减法，负数的减法与等价的正数相同。通过在调整符号后使add和减法相互调用，可以节省大量代码。

4 /避免从小数中减去大数，因为您总是会得到如下数字：

         10
         11-
-- -- -- --
99 99 99 99 (and you still have a borrow).

而是从11中减去10，然后取反：

11
10-
--
 1 (then negate to get -1).

这是我必须为此做的其中一个库的注释（变成了文本）。不幸的是，该代码本身已受版权保护，但是您可以选择足够的信息来处理这四个基本操作。在下面假定 -a和 -b表示负数，并且 a和 b是零或正数。

另外，如果符号不同，请使用负数相减：

-a +  b becomes b - a
 a + -b becomes a - b

对于减法，如果符号不同，请使用加法运算符：

 a - -b becomes   a + b
-a -  b becomes -(a + b)

还要进行特殊处理以确保我们从大数中减去小数：

small - big becomes -(big - small)

乘法使用入门级数学，如下所示：

475(a) x 32(b) = 475 x (30 + 2)
               = 475 x 30 + 475 x 2
               = 4750 x 3 + 475 x 2
               = 4750 + 4750 + 4750 + 475 + 475

实现此目的的方法包括一次提取32个数字中的每个数字（向后），然后使用加法计算要添加到结果中的值（最初为零）。

ShiftLeft和 ShiftRight操作用于快速将 LongInt除以换位值（对于“实数”数学为10）。在上面的示例中，我们将475加到零2次（最后一位数字32）得到950（结果= 0 + 950 = 950）。

然后我们左移475以获得4750，向右移32以获得3。将4750归零3次以获得14250，然后加到950的结果以获得15200。

左移4750可获得47500，右移3可获得0。由于右移32现在为零，因此我们完成了，实际上475 x 32等于15200。

除法也很棘手，但是基于早期的算术（“进”的“ gazinta”方法）。考虑以下 12345 / 27的长除法：

       457
   +-------
27 | 12345    27 is larger than 1 or 12 so we first use 123.
     108      27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
     ---
      154     Bring down 4.
      135     27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
      ---
       195    Bring down 5.
       189    27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
       ---
         6    Nothing more to bring down, so stop.

因此， 12345 / 27是 457，其余为 6。校验：

  457 x 27 + 6
= 12339    + 6
= 12345

这是通过使用一个下拉变量（最初为零）来一次将12345的各段降低一个，直到大于或等于27来实现的。

然后，我们简单地从中减去27，直到降至27以下-相减的次数就是添加到最上面一行的部分。

当没有更多细分可放时，我们得到了结果。



请记住，这些是非常基本的算法。如果您的数字特别大，则有更好的方法进行复杂的算术运算。您可以查看 GNU Multiple Precision Arithmetic Library之类的东西-它比我自己的库快得多，而且更好。

它确实有一个不幸的功能，就是如果它用完了内存就会退出（我认为这对于通用库来说是一个致命的缺陷），但是，如果您能够超越它，那么它的功能就相当不错了。

如果您出于许可原因不能使用它（或者因为不想让应用程序退出而没有明显的原因），则至少可以从中获取用于集成到自己的代码中的算法。

我还发现， MPIR（GMP的一个分支）上的身体更适合讨论潜在的变化-它们似乎对开发人员更友好。