biginteger - BigNums 实现如何工作？

Question

我想知道 BigInt 和其他类似的东西是如何实现的。我试图查看 JAVA 源代码，但对我来说全是希腊语和拉丁语。您能否用文字向我解释一下该算法 - 没有代码，以便我了解当我使用 JAVA API 中的某些内容时我实际使用的是什么。问候

Answer 1

从概念上讲，这与手动进行任意大小算术的方式相同。您有一个值数组之类的东西，以及用于该数组的各种操作的算法。

假设您要将 100 添加到 901。您从两个数字作为数组开始:

 [0, 1, 0, 0]
 [0, 9, 0, 1]

当你添加时，你的加法算法从右边开始，取0+1，给出1，0+0，给出0，然后 - 现在是棘手的部分 - 9+1 给出 10，但现在我们需要进位，所以我们加 1结束下一列，并将 (9+1)%10 放入第三列。

当您的数字变得足够大时(在本例中大于 9999)，那么您必须以某种方式分配更多空间。

当然，如果您以相反顺序存储数字，这会有所简化。

真正的实现使用完整的单词，因此模数实际上是 2 的某个大幂，但概念是相同的。

Knuth 对此有一个非常好的部分。