任意精度算术解释
我试图学习C，并遇到无法使用真正的大数字（即100位数，1000位数等）。 我知道存在这样的库，但我想尝试自己实现它。
我只想知道任何人是否有或可以提供任意精度算术的非常详细的，简单的解释。
将数字视为较小的部分都是足够的存储和algorithm的问题。 我们假设你有一个编译器，其中int只能是0到99，而你想处理的数字可以达到999999（为了保持简单，我们只会担心正数）。
你这样做是通过给每个数字三个int并使用你（应该有的）在小学学到的相同规则来进行加法，减法和其他基本操作。
在任意一个精确的库中，用于表示我们的数字的基本types的数量没有固定的限制，只要内存可以容纳即可。
另外例如： 123456 + 78 ：
12 34 56 78 -- -- -- 12 35 34
从最不重要的一点开始工作：
- 初始进位= 0。
- 1进位56 + 78 + 0进位= 134 = 34
- 34 + 00 + 1进位= 35 = 35进位
- 12 + 00 + 0进位= 12 = 12进位
实际上，这是在CPU内部的位级上的加法。
减法是类似的（使用基types的减法和借位代替进位），乘法可以用重复的加法（非常缓慢）或交叉乘积（加快）来完成，除法可以通过移位和减法来完成参与（你将从小时候开始学习的很长一段时间）。
我实际上编写了库来做这种东西，使用十的最大幂可以适合一个整数时平方（防止溢出，当两个int相乘在一起，如16位int被限制在0到99时产生9,801（<32,768）时，或32位int使用0到9,999产生99,980,001（<2,147,483,648）），这大大缓解了algorithm。
一些技巧要注意。
1 /当添加或乘以数字时，预先分配所需的最大空间，如果发现太多，则稍后再减less。 例如，添加两个100-“数字”（其中数字是一个int ）数字将永远不会给你多于101位数字。 将12位数字乘以3位数字永远不会生成超过15位数字（加上数字计数）。
2 /为了增加速度，只有在绝对必要的时候才进行标准化（减less所需的存储空间） – 我的数据库把这个作为一个单独的调用，这样用户就可以在速度和存储问题之间做出决定。
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)
乘法使用入门级math如下：
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来计算要加到结果（最初为0）的值。
ShiftLeft和ShiftRight操作用于快速乘以或除以一个LongInt的换行值（“真实”math为10）。 在上面的例子中，我们添加475到零2次（最后一位32）得到950（结果= 0 + 950 = 950）。
然后我们左移475得到4750右移32得到3.加4750到零3倍得到14250然后加950的结果得到15200。
左移4750得到47500，右移3得到0.由于右移32现在为零，我们完成了，实际上475×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
这是通过使用一个下拉variables（最初为零）来实现一次一个下降12345的段，直到它大于或等于27。
然后，我们简单地从中减去27，直到我们得到27以下 – 减法的数量是添加到顶部的线段。
当没有更多的部分可以打倒的时候，我们得到了我们的结果。
请记住这些是非常基本的algorithm。 如果你的数字特别大，有更好的方法来做复杂的算术。 你可以看看像GNU多精度算术库 – 这是比我自己的图书馆更好，更快。
它有一个相当不幸的错误之处，就是它只会在内存不足的情况下退出（在我看来，这对于一个普通用途的图书馆来说是一个相当致命的缺陷），但是如果你能从中看出这个缺点，那么它的function就相当不错了。
如果您不能将其用于授权原因（或者因为您不希望自己的应用程序刚刚退出而无任何理由），那么您至less可以从中获得用于集成到您自己的代码中的algorithm。
我还发现，MPIR（GMP的一个分支）上的BOD更容易讨论潜在的变化 – 它们似乎更适合开发者。
重新发明轮子对你个人的熏陶和学习来说是非常好的，同时也是一个非常大的任务。 我不想阻止你作为一个重要的工作，而是我自己做的一个重要的工作，但是你应该知道，在大型软件包的工作中存在一些微妙和复杂的问题。
例如，乘法。 天真地说，你可能会想到“男生”的方法，即写一个数字在另一个数字之上，然后按照你在学校学到的那样进行长时间乘法。 例：
123 x 34 ----- 492 + 3690 --------- 4182
但是这个方法非常慢（O（n ^ 2），n是数字的个数）。 相反，现代的bignum软件包使用离散傅里叶变换或数值变换来将其变成本质上的O（n ln（n））运算。
这只是整数。 当你在数字（log，sqrt，exp等）的某种真实表示方式上遇到更复杂的函数时，情况会变得更加复杂。
如果您需要一些理论背景，我强烈推荐阅读Yap “algorithm代数的基本问题”一书的第一章。 如前所述，gmp bignum图书馆是一个很好的图书馆。 对于实际的数字，我使用mpfr并喜欢它。
不要重新发明轮子：它可能会变成方形的！
使用经过testing的第三方库，如GNU MP 。
你可以用高中的math水平来做。 尽pipe现实中使用了更高级的algorithm。 所以例如要添加两个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 ++构build的。 上面的例子是愚蠢的，但这是一般的加减法。
关于这个问题的一个很好的参考是math运算的计算复杂性 。 它会告诉您每个要执行的操作需要多less空间。 例如，如果您有两个N-digit数字，则需要2N digits来存储乘法结果。
正如Mitch所说，实施起来并不是一件容易的事情！ 如果您了解C ++，我build议您看一下TTMath。
你用铅笔和纸做的方式基本一样
- 该数字将被表示为一个缓冲区（数组），可以根据需要采取任意大小（这意味着使用
malloc和realloc） - 您尽可能使用语言支持的结构来实现基本算术，并手动处理载体和移动小数点
- 您可以冲刷数字分析文本以查找更复杂函数处理的有效参数
- 你只需要实现尽可能多的。
通常，您将使用您作为计算的基本单位
- 包含0-99或0-255的字节
- 16位字包含0-9999或0–65536
- 32位字包含…
- …
如你的架构所规定的。
二进制或十进制基数的select取决于您希望获得最大的空间效率，人的可读性以及芯片上是否缺less二进制编码十进制（BCD）math支持。
最终的参考文献之一（恕我直言）是Knuth的TAOCP第二卷。 它解释了许多用于在这些表示上表示数字和算术运算的algorithm。
@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}, }
假设你想自己编写一个大的整数代码，这可能会非常简单，就像最近做的那样（尽pipe在MATLAB中）。下面是我使用的一些技巧：
-
我将每个单独的十进制数字存储为一个双精度数。 这使得许多操作变得简单，特别是输出。 虽然它占用的内存比你想要的要多，但是内存在这里很便宜，而且如果你可以有效地对一对向量进行卷积的话，它的乘法效率会非常高。 或者，您可以在一个double中存储几个十进制数字，但要小心的是，卷积来进行乘法运算可能会导致大数目的数值问题。
-
分别存储一个符号位。
-
增加两个数字主要是增加数字，然后在每一步检查进位。
-
一对数字的乘法最好是卷积后跟一个进位步骤，至less如果你有一个快速的卷积码。
-
即使将数字存储为单个十进制数字的string，除法（也可以是mod / rem操作）可以在结果中一次获得大约13位十进制数字。 这比一次仅处理一位十进制数字的分隔更有效率。
-
要计算一个整数的整数次幂，计算指数的二进制表示。 然后使用重复的平方运算来根据需要计算权力。
-
许多操作（因式分解，素性testing等）将受益于powermod操作。 也就是说，当你计算mod（a ^ p，N）时，在指数化的每一步中减less结果mod N，其中p已经以二进制forms表示。 先不计算^ p，然后尝试减lessmod N.
这是我在PHP中做的一个简单的（天真的）例子。
我实现了“Add”和“Multiply”，并将其用于指数示例。
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); }
