math - 任意精度算术说明

Question

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

我只是想知道是否有人已经或可以提供对任意精度算术的非常详细、简单的解释。

score 172 · Accepted Answer

这完全取决于足够的存储空间和算法来将数字视为较小的部分。假设您有一个编译器，其中 anint只能是 0 到 99，并且您想处理最大为 999999 的数字（为了简单起见，我们只担心正数）。

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

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

加法例如123456 + 78：：

从最不重要的一端开始工作：

初始进位 = 0。
56 + 78 + 0 进位 = 134 = 34 有 1 个进位
34 + 00 + 1 进位 = 35 = 35 与 0 进位
12 + 00 + 0 进位 = 12 = 12 0 进位

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

减法类似（使用基本类型的减法和借位而不是进位），乘法可以通过重复加法（非常慢）或叉积（更快）来完成，除法更棘手，但可以通过数字的移位和减法来完成参与（你小时候会学的长除法）。

我实际上已经编写了库来使用最大的 10 次方来做这类事情，当平方时可以适合整数（以防止在将两个ints 相乘时溢出，例如 16 位int被限制为 0 到 99 到平方时生成 9,801 (<32,768)，或者使用 0 到 9,999 生成 32 位int99,980,001 (<2,147,483,648))，这极大地简化了算法。

需要注意的一些技巧。

1/ 加法或乘法时，预先分配所需的最大空间，如果发现太多，以后再减少。例如，添加两个 100-“digit”（其中 digit 为int）数字永远不会超过 101 位。将 12 位数字乘以 3 位数字永远不会产生超过 15 位数字（添加数字计数）。

2/ 为了提高速度，仅在绝对必要时才对数字进行标准化（减少所需的存储空间）——我的图书馆将此作为单独的调用，因此用户可以在速度和存储问题之间做出决定。

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

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 个数字中的每一个（向后），然后使用 add 计算要添加到结果中的值（最初为零）。

ShiftLeft和ShiftRight运算用于快速将 aLongInt除以换行值（“真实”数学为 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 的一个分支）的 bods更愿意讨论潜在的变化——它们似乎对开发人员更友好。

score 10 · Accepted Answer

虽然重新发明轮子对您的个人启蒙和学习非常有好处，但它也是一项艰巨的任务。我不想劝阻你，因为它是一项重要的练习，也是我自己完成的，但你应该知道，更大的包解决了一些微妙而复杂的问题。

例如，乘法。天真地，你可能会想到“小学生”的方法，即把一个数字写在另一个上面，然后像你在学校学到的那样做长乘法。例子：

      123
    x  34
    -----
      492
+    3690
---------
     4182

但是这种方法非常慢（O（n ^ 2），n是位数）。相反，现代 bignum 包使用离散傅立叶变换或数值变换将其转换为本质上 O(n ln(n)) 的操作。

这仅适用于整数。当您在某种类型的数字真实表示（log、sqrt、exp 等）上使用更复杂的函数时，事情会变得更加复杂。

如果您想了解一些理论背景，我强烈建议您阅读 Yap 的书“算法代数的基本问题”的第一章。如前所述，gmp bignum 库是一个优秀的库。对于实数，我使用了MPFR并喜欢它。

score 7 · Accepted Answer

不要重新发明轮子：结果可能是方形的！

使用经过试验和测试的第三方库，例如GNU MP 。

score 4 · Accepted Answer

你用铅笔和纸做的基本相同的方式......

该数字将在能够根据需要采用任意大小（这意味着使用mallocand realloc）的缓冲区（数组）中表示
您使用语言支持的结构尽可能地实现基本算术，并手动处理进位和移动小数点
您搜索数字分析文本以找到更复杂的函数处理的有效参数
你只需要尽可能多地实施。

通常你会使用你的基本计算单位

包含 0-99 或 0-255 的字节
包含 0-9999 或 0--65536 的 16 位字
32位字包含...
...

由您的架构决定。

二进制或十进制基数的选择取决于您对最大空间效率、人类可读性以及芯片上是否缺少二进制编码十进制 (BCD) 数学支持的期望。

score 3 · Accepted Answer

最终参考资料之一（恕我直言）是 Knuth 的 TAOCP 第 II 卷。它解释了许多用于表示数字的算法以及对这些表示的算术运算。

@Book{Knuth:taocp:2,
   author    = {Knuth, Donald E.},
   title     = {The Art of Computer Programming},
   volume    = {2: Seminumerical Algorithms, second edition},
   year      = {1981},
   publisher = {\Range{Addison}{Wesley}},
   isbn      = {0-201-03822-6},
}

score 3 · Accepted Answer

你可以用高中数学水平做到这一点。尽管在现实中使用了更高级的算法。因此，例如添加两个 1024 字节的数字：

unsigned char first[1024], second[1024], result[1025];
unsigned char carry = 0;
unsigned int  sum   = 0;

for(size_t i = 0; i < 1024; i++)
{
    sum = first[i] + second[i] + carry;
    carry = sum - 255;
}

one place在添加处理最大值的情况下，结果必须更大。看这个：

9
   +
9
----
18

如果您想学习，TTMath是一个很棒的库。它是使用 C++ 构建的。上面的例子很愚蠢，但加法和减法通常是这样完成的！

关于该主题的一个很好的参考是数学运算的计算复杂性。它告诉您要实现的每个操作需要多少空间。例如，如果您有两个N-digit数字，则需要2N digits存储相乘的结果。

正如Mitch所说，实现起来远不是一件容易的事！如果你了解 C++，我建议你看看 TTMath。

score 1 · Accepted Answer

假设您希望自己编写一个大整数代码，这可能非常简单，就像最近做过的人一样（尽管是在 MATLAB 中）。以下是我使用的一些技巧：

我将每个单独的十进制数字存储为双数。这使得许多操作变得简单，尤其是输出。虽然它确实占用了比您希望的更多的存储空间，但这里的内存很便宜，如果您可以有效地对一对向量进行卷积，它会使乘法非常有效。或者，您可以将多个十进制数字存储在双精度数中，但要注意进行乘法运算的卷积可能会导致非常大的数字出现数值问题。
单独存储一个符号位。
两个数字相加主要是数字相加，然后在每一步检查进位。
一对数字的乘法最好在卷积之后进行进位步骤，至少如果您有一个快速卷积码可用。
即使您将数字存储为一串单独的十进制数字，也可以进行除法（也称为 mod/rem ops）以在结果中一次获得大约 13 个十进制数字。这比一次只处理 1 个十进制数字的除法要有效得多。
要计算整数的整数幂，请计算指数的二进制表示。然后根据需要使用重复的平方运算来计算幂。
许多操作（因式分解、素数测试等）将从 powermod 操作中受益。也就是说，当您计算 mod(a^p,N) 时，在取幂的每个步骤中减少结果 mod N，其中 p 以二进制形式表示。不要先计算 a^p，然后尝试减少它 mod N。

score 0 · Accepted Answer

这是我在 PHP 中做的一个简单（天真的）示例。

我实现了“加法”和“乘法”并将其用于指数示例。

http://adevsoft.com/simple-php-arbitrary-precision-integer-big-num-example/

代码片段

// Add two big integers
function ba($a, $b)
{
    if( $a === "0" ) return $b;
    else if( $b === "0") return $a;

    $aa = str_split(strrev(strlen($a)>1?ltrim($a,"0"):$a), 9);
    $bb = str_split(strrev(strlen($b)>1?ltrim($b,"0"):$b), 9);
    $rr = Array();

    $maxC = max(Array(count($aa), count($bb)));
    $aa = array_pad(array_map("strrev", $aa),$maxC+1,"0");
    $bb = array_pad(array_map("strrev", $bb),$maxC+1,"0");

    for( $i=0; $i<=$maxC; $i++ )
    {
        $t = str_pad((string) ($aa[$i] + $bb[$i]), 9, "0", STR_PAD_LEFT);

        if( strlen($t) > 9 )
        {
            $aa[$i+1] = ba($aa[$i+1], substr($t,0,1));
            $t = substr($t, 1);
        }

        array_unshift($rr, $t);
     }

     return implode($rr);
}

math - 任意精度算术说明

8 回答 8

Related

Reference