有没有GMP的限制？

Question

所有的GMP文件似乎都暗示着没有限制。这真的是真的吗？在

我想做一些简单的整数运算（加法、移位、异或、乘法、除法等），但是真正的大数是2^2^96（即2^79228162514264337593543950336，可能比你的计算机内存多出几个数量级），甚至2^2^256。如果我费尽心机去搞GMP并对其进行编码，会不会让它对我提出如此超乎寻常的数字感到惊讶呢，还是会像大肆宣传的那样奏效呢？在

我希望在Java中使用它，所以我可能会使用jnigmphere，但我对语言不是很挑剔。Python看起来可以与GMP一起工作。在

Answer 1

Are there any limits to GMP?

是的，有。在两个方面。在

• 真正大的数字需要大量的内存。@hexafraction的答案探究了这一点。

• 对大量数据进行操作需要很长时间。例如，添加两个N位数字需要O(N)操作。将两个N位数相乘就是超线性¹。（假设为非压缩表示…）

  好吧，这不是一个限制，因为你碰到了一个硬障碍。但是如果你的程序要花很长时间才能运行，那显然是一个实用的限制。

也有一些关于GMP是否压缩的讨论。答案有很多种：

• 看看GMP源代码。（@hexafraction说答案是“不压缩”）

• 试着做个实验。编写一个小程序，通过左移1来创建（比如）2^1000000000，并使用top或等效函数来查看程序使用了多少内存。

• 考虑压缩对算术运算的影响。事实上，最后一种方法可能是最有启发性的。它将告诉您对于一个通用（或特殊用途）bignum库使用压缩是否可行。

^{1-朴素的长乘法是O(N^2)，但是有更好的算法具有更好的渐近性能。对于2^2^96区域内的数字，您应该查看Schönhage–Strassen algorithm，或Fürer's algorithm。一般来说，multiplication algorithms上的维基百科页面是开始阅读的好地方。}

使用NUBIGMS压缩算法

假设我们这样做的原因是数字太大，无法以未压缩的形式表示。因此，解压缩操作数，执行运算并压缩结果。。。不是一个可行的选择。在

如果您尝试对压缩的数字应用普通的算术算法，那么您需要能够逐步地对输入进行解压缩，执行操作，并压缩输出。这可行吗？那要看细节了。例如：

• 若要将两个数字相加，请从最低有效位开始，再加上相应的位，进位并重复。完整的操作需要一次通过输入数字。如果你的压缩方案是一个稀疏的位数组，那就可以了，但是如果你使用的是游程编码，那么你就需要对从最低有效位到最高有效位的运行进行编码。

• 要将两个数相乘，基本上需要进行N位移位并将序列相加N次。这也可以逐步完成。但请注意，我们正在对每个移位和加法循环进行增量解压缩/压缩。。。

• 将除。。。你做N位移位和N次减法。同上。

但有两个问题：

• 压缩/解压缩会给所有这些操作增加开销。假设您选择了一个合适的压缩方案，开销将是每位压缩/解压缩的常数乘数。

• 第二个问题是压缩方案在输入和输出以及更复杂操作的中间结果上是否实际有效。

那么还有其他选择吗？在

很可能是的。如果你使用游程编码，你可以写（比如）一个加法算法，它考虑到“运行”。例如：

     10000000000000001
    +10000000000000001

• 将最左边的数字对相加

                  10
  

• 添加匹配的零

    0000000000000010
  

• 添加MSB

  100000000000000010
  

然后你就可以建立更复杂的操作了。在

这种方法的优点（如果你能做到的话）是，对于合适的输入，它将降低复杂度计算的有效性。例如，加法现在比O(N)好。（我认为它实际上应该与游程编码表示的大小成比例…）

但是，这又一次使操作变得更加复杂，并且只有当运行的平均长度足够大以补偿时才会有效。对于压缩得不够好的数字，这将是一个反优化。在

---

总而言之：

1. 这种方法的可行性取决于实际数字的可压缩性。

2. 值得怀疑的是，在一个通用“大数”库（如GMP）中，这是否是一个可行的方法。我们在数值环境中遇到的典型的大数字是不可压缩的。。。在某种程度上会有帮助。如果压缩没有帮助的话，可能会阻碍。

3. 如果存在这样一个特殊用途的“大数”库，这可能是可行的。在适当的情况下，压缩算法的复杂度应优于普通的bignum算法。

Answer 2

是的，是的。它会尝试对你给出的任何数字进行存储和操作，尽管在许多情况下，类似于你的问题将变得不合理。在

实际上，操作系统和计算机硬件是有限制的。在

2^2^96用2^96位表示最佳未压缩情况。这相当于只有9904000000000兆兆兆字节。你的计算机不能存储那么多数据。此外，只能索引一个高达40亿左右的数组，不足以管理这一巨大的数据堆。为了处理每一个位，我们需要一个40亿个入口数组，一个40亿个入口数组，一个40亿个入口数组。我不太确定是否允许，因为总元素超过40亿。在

不管怎样，在32位JVM上，堆的最大值为4gb。在这一点上，即使你可以存储这么多比特，你以4 GB/秒的速度进行操作，也需要784.6亿年的时间。在

即使数字可以被压缩（必须进行一定程度的解压）以进行操作，您仍然需要考虑到90亿TB数据的Kolmogrov complexity不太可能小于真实数字的一整TB。在