java - GMP有任何限制吗？

Question

所有的GMP文件似乎都暗示着没有限制。这是真的吗？
我想做一些简单的整数运算（加法、移位、异或、乘法、除法等），但真正的大数是2^2^96（即2^79228162514264337593543950336，这可能比你电脑的内存大几个数量级），甚至是2^2^256。如果我去麻烦得到GMP和编码反对它，它会扬眉吐气，因为我要求如此非同寻常的数字，还是它只是工作-正如炒作建议？
我希望在Java中使用它，所以我可能会使用JNI GMPhere，但我对语言并不是很挑剔。Python看起来可以与GMP一起工作。

Answer 1

GMP有什么限制吗？
是的。在两个方面。
大量的数据需要大量的内存。@六分式的答案探索了这一点。
对大量数据的操作需要很长时间。例如，添加两个N位数字需要O(N)操作。两个N位数字相乘是超线性1。（假设非压缩表示…）
好吧，这不是一个极限，因为你遇到了一个很难的障碍。但是，如果你的程序要花很长时间才能运行，这显然是一个实际的限制。
还有一些关于GMP是否能压缩的讨论。有很多方法可以回答这个问题：
看看GMP源代码。（@hexafraction说答案是“不压缩”）
试试做个实验。编写一个小程序，通过左移1来创建（比如）2100000000，并使用top或等效程序来查看程序使用了多少内存。
考虑压缩对算术运算的影响。事实上，最后一种方法可能是最有启发性的。它将告诉您通用（或专用）bignum库是否可以使用压缩。
1-朴素的长乘法是O(N^2)，但是有更好的算法具有更好的渐近性能。对于2^2^96区域内的数字，您应该查看Schönhage–Strassen algorithm或Fürer's algorithm。一般来说，在multiplication algorithms上的维基百科页面是开始阅读的好地方。
使用压缩bignum的算法
假设我们这样做的原因是数字太大，无法用未压缩的形式表示。所以解压操作数，做操作，压缩结果。。。不是一个可行的选择。
如果尝试对压缩的数字应用普通的算术算法，则需要能够以增量方式解压缩输入、执行操作和压缩输出。这可行吗？那要看细节了。例如：
要添加两个数字，至少从有效结尾开始，然后添加相应的位，进位并重复。完整的操作需要输入数字的一次传递。如果你的压缩方案是（比如）一个稀疏的位数组，那么这是可行的，但是如果你使用了运行长度编码，那么你就需要对从最低有效位到最高有效位的运行进行编码。
要将两个数字相乘，基本上要进行N位移位，并将序列N次相加。这也可以逐步完成。但请注意，我们正在对每个移位和添加周期执行增量解压缩/压缩。。。
分开。。。你做N位移位，然后减去N次。同上。
但有两个问题：
压缩/解压缩为所有这些操作增加了开销。假设您选择了合适的压缩方案，那么每压缩/解压缩一位的开销将是一个常数乘数。
第二个问题是压缩方案在输入和输出以及在更复杂的操作中的中间结果上是否真的有效。
那么还有别的选择吗？
很可能是的。如果您使用运行长度编码，您可以编写（比如）一个加法算法，该算法将“运行”考虑在内。例如：

     10000000000000001
    +10000000000000001

将最左边的两个数字相加

                10

添加匹配的零行

  0000000000000010

添加MSBs

100000000000000010

然后你可以从中建立更复杂的操作。
这种方法的优点（如果你能把它拉开）是，对于合适的输入，它将降低计算的复杂性。例如，加法现在比O(N)好。（我认为它实际上应该与运行长度编码表示的大小成比例…）
但这又一次使操作变得更加复杂，并且只有当平均运行时间足够长以进行补偿时才会有效。对于压缩得不够好的数字，这将是一种反优化。
总而言之：
这种方法的可行性取决于实际数字的可压缩性。
在通用的“大数字”库（如GMP）中，这种方法是否可行值得怀疑。我们在数值环境中遇到的典型的大数是不能充分压缩的。。。在某种程度上会有帮助。如果压缩不起作用，它可能会阻碍。
这可能是可行的，在一个特殊用途的“大数”图书馆，只要有这样一个图书馆存在。在适当的情况下，压缩算法比常规BIGUM算法具有更好的复杂度。