任意精度算术解释

https://stackoverflow.com/questions/1218149

10-07-2019
|

题

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

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

解决方案

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

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

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

添加例如： 123456 + 78:

从最低有效端开始工作：

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

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

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

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

一些需要注意的技巧。

1/ 当数字相加或相乘时，预先分配所需的最大空间，然后如果发现太多则减少。例如，添加两个 100-“数字”（其中数字是 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 运算用于快速乘法或除法 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 多精度算术库 - 它比我自己的库更好更快。

它确实有一个相当不幸的错误功能，因为如果内存不足，它就会简单地退出（在我看来，对于通用库来说这是一个相当致命的缺陷），但是，如果你能忽略这一点，它的功能非常好。

如果您因许可原因而无法使用它（或者因为您不希望您的应用程序无缘无故地退出），您至少可以从那里获取算法以集成到您自己的代码中。

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

其他提示

虽然重新发明轮子非常适合您的个人教育和学习，但它也是一项非常大的任务。我不想劝阻你作为一项重要的练习，也不是我自己完成的练习，但是你应该意识到大型课程所涉及的工作中存在微妙而复杂的问题。

例如，乘法。天真地，你可能会想到“小学生”的方法，即在一个数字之上写一个数字，然后在学校学习时进行长时间的乘法。例如：

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

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

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

如果您有一些理论背景，我强烈建议您阅读Yap的书的第一章， <！>“算法代数的基本问题<！> 。如前所述，gmp bignum库是一个很好的库。对于实数，我使用了mpfr并喜欢它。

不要重新发明轮子：它可能会变成方形！

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

您的操作方式基本上与使用铅笔和纸相同...

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

通常您将使用作为基本计算单位

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

由您的架构决定。

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

你可以用高中数学水平做到这一点。虽然现实中使用了更先进的算法。例如，添加两个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。

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

@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},
}

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

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

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

我实现了<！>“添加<！>”;和<！>“;乘以<！>”;并将其用于指数示例。

http://adevsoft.com/simple-php -arbitrary精度整数-大NUM-示例/

代码片段

// 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);
}

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow

任意精度算术 解释

任意精度算术解释