我正在学习C语言，遇到了无法处理非常大的数字（例如100位、1000位等）的问题。我知道有现成的库可以做到这一点，但我想尝试自己实现它。
我只是想知道是否有人能提供一个非常详细而通俗易懂的任意精度算术解释。
8个回答
181
关键在于充足的存储和将数字视为较小部分的算法。让我们假设你有一个编译器，其中一个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，不带进位
- 12 + 00 + 0 进位=12 = 12，不带进位
实际上，这就是在CPU内部以位为单位进行加法运算的方式。
减法类似（使用基类型的减法和借位），乘法可以通过重复加法（非常慢）或叉积（更快）来完成，而除法则更加棘手，但可以通过移位和涉及数字的减法（作为儿童学习的长除法）来完成。
事实上，我曾经编写过库来执行此类操作，其中使用了可容纳两个int相乘时的最大十次幂（例如一个16位的int在0到99之间生成9,801（<32,768）时，或32位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
ShiftLeft和ShiftRight操作用于快速将LongInt乘以或除以包装值（“真实”数学为10）。在上面的示例中，我们将475加两次（32的最后一位数字为2），将其加到零上得到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的分支）更愿意讨论潜在的变化-他们似乎是一个更友好的开发人员团队。
- paxdiablo
2
17我认为你很好地涵盖了“我只想知道是否有人可以提供非常详细、通俗易懂的任意精度算术解释”的内容。 - Grant Peters
一个后续问题：在没有访问机器代码的情况下，是否可能设置/检测进位和溢出？ - SasQ
13
虽然重新发明轮子对于个人的教育和学习非常有益，但这也是一项极其艰巨的任务。我不想劝阻你，因为这是一项重要的练习，我自己也做过，但你应该意识到存在微妙而复杂的问题，而大型软件包可以解决这些问题。
例如，乘法。天真地说，你可能会想到“小学生”方法，即将一个数字写在另一个数字上方，然后像在学校学习的那样进行长乘法。例如：
123
x 34
-----
492
+ 3690
---------
4182
但是这种方法非常缓慢（O（n ^ 2），n代表数字的数量）。 相反，现代bignum包使用离散傅里叶变换或Numeric变换将其转换为基本上是O（nln（n））的操作。
而且这仅适用于整数。 当您涉及某些类型实数表示的更复杂函数（对数，平方根，指数等）时，事情变得更加复杂。
如果您想了解一些理论背景，我强烈建议阅读Yap的书的第一章“Algorithmic Algebra的基本问题”。 如前所述，gmp bignum库是一个优秀的库。 对于实数，我使用过MPFR并喜欢它。
- froofroo
2
2我对“使用离散傅里叶变换或数值变换将其转化为基本上是O(n ln(n))操作”的部分很感兴趣，这是如何工作的？只需要一个参考就可以了 :) - detly
2@detly：多项式乘法与卷积相同，使用FFT执行快速卷积的信息应该很容易找到。任何数字系统都是一个多项式，其中数字是系数，基数是基数。当然，您需要注意进位以避免超出数字范围。 - Ben Voigt
7
不要重复造轮子：它可能会变成方形！
使用第三方库，如GNU MP，这是经过验证的。
- Mitch Wheat
5
4如果你想学习 C 语言，建议你的目标设定低一些。实现一个大数库对于初学者来说并不容易，有各种微妙的原因会让他们遇到困难。 - Mitch Wheat
3第三方库：同意，但 GMP 存在许可证问题（LGPL，但实际上它的行为类似于 GPL，因为通过 LGPL 兼容接口进行高性能数学计算有点困难）。 - Jason S
很不错的《飞出个未来》参考（有意为之？） - Grant Peters
9GNU MP 在遇到某些非常大的计算时，如果出现内存分配失败，会无条件地调用
abort() 函数。这种行为对于一个库来说是不可接受的，并足以成为编写自己的任意精度代码的理由。请注意保持原文意思不变，同时将语言更改为通俗易懂的方式。 - R.. GitHub STOP HELPING ICE我必须同意R的观点。当内存不足时，一个简单地从程序中抽出地毯的通用库是不可原谅的。我宁愿他们为了安全性/可恢复性而牺牲一些速度。 - paxdiablo
4
你可以用与纸笔相同的方式来完成以下操作...
- 将数字表示为缓冲区（数组），能够根据需要使用
malloc和realloc进行任意调整大小 - 尽可能使用语言支持的结构实现基本算术，并手动处理进位和移动小数点
- 查阅数字分析文本以找到处理更复杂函数的有效参数
- 只实现所需内容。
通常，您将使用以下作为计算的基本单位
- 包含0-99或0-255的字节
- 包含0-9999或0-65536的16位字
- 包含...的32位字
- ...
这取决于您对最大空间效率、人类可读性以及芯片上是否存在二进制编码十进制（BCD）数学支持的期望。
- dmckee --- ex-moderator kitten
3
你可以用高中数学水平完成这个任务。虽然在实际中使用更高级的算法。例如，要添加两个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;
}
在加法运算中，为了处理最大值，结果将需要增加一个位置。请看下面的例子：
9
+
9
----
18
TTMath是一个很棒的库，如果你想学习的话。它是用C++构建的。上面的例子有点傻，但这就是一般情况下加减法的实现方式！
关于这个主题的一个好参考是数学操作的计算复杂度。它告诉你每个你想要实现的操作需要多少空间。例如，如果你有两个N位数，那么你需要2N位数来存储乘法的结果。
正如Mitch所说，这绝对不是一个容易实现的任务！我建议你如果懂C++的话可以看看TTMath。
- Khaled Alshaya
4
我确实考虑过使用数组，但我正在寻找更通用的东西。感谢您的回复！ - TT.
3嗯...提问者的名字和图书馆的名字不可能是巧合，是吧？ ;) - John Y
LoL，我没注意到！我真希望TTMath是我的 :) 顺便说一下，这是我关于这个主题的一个问题： - Khaled Alshaya
https://dev59.com/6HNA5IYBdhLWcg3wNrAy - Khaled Alshaya
3
在我看来，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},
}
- Marc van Dongen
1
假设你希望自己编写一个大整数代码，这其实很简单，就像我最近所做的一样（尽管是在MATLAB中）。以下是我使用的一些技巧：
我将每个十进制数字存储为双精度数。这使得许多操作变得简单，特别是输出。虽然它占用的存储空间比您希望的要多，但在这里内存很便宜，如果您可以有效地卷积一对向量，则可以使乘法非常高效。或者，您可以将几个十进制数字存储在一个双精度数中，但请注意，在进行乘法的卷积时，可能会在非常大的数字上引起数值问题。
将符号位单独存储。
两个数字的加法主要是将数字相加，然后在每个步骤检查进位。
一对数字的乘法最好通过卷积后跟随一个进位步骤来完成，至少如果您有快速卷积代码的话。
即使将数字存储为单个十进制数字的字符串，也可以执行除法（还包括模/余数运算），以在结果中获得大约13个十进制数字。这比仅逐个十进制数字工作的除法要高效得多。
要计算整数的幂，计算指数的二进制表示。然后使用重复平方操作根据需要计算幂。
许多操作（分解质因数，素性测试等）将受益于powermod操作。也就是说，在计算mod(a^p,N)时，在指数的每个步骤上将结果缩小到N。不要先计算a^p，然后尝试将其缩小到N。
- user85109
1
1如果你存储的是单个数字，而不是十进制的10 ^ 9或类似的2 ^ 32，那么所有花哨的卷积乘法都是浪费。当常量太糟糕时，大O几乎毫无意义... - R.. GitHub STOP HELPING ICE
0
这是我在 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);
}
- kervin
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接