2

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

我想做一些简单的整数数学运算（加法、移位、异或、乘法、除法等），但真正巨大的数字高达 2^2^96（即 2^79,228,162,514,264,337,593,543,950,336，这可能比你的内存多几个数量级有在你的电脑）或什至 2^2^256。如果我费尽心思获得 GMP 并针对它进行编码，它会因为我要求如此非凡的数字而对我挑眉还是会像炒作所暗示的那样工作？

我希望将它与 Java 一起使用，所以我可能会在这里使用 JNI GMP，但我对语言并不是很挑剔。Python 看起来可以与 GMP 一起使用。

4

3 回答 3

4

GMP有任何限制吗？

是的，有。在两个方面。

  • 非常大的数字需要大量内存。@hexafraction 的回答探讨了这一点。

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

    好的，所以从你遇到硬障碍的意义上说，这不是一个限制。但是，如果您的程序需要很长时间才能运行，那显然是一个实际限制。

关于GMP是否进行压缩也有一些讨论。有很多方法可以回答这个问题：

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

  • 尝试一个实验。编写一个小程序，通过左移 1来创建（比如说）2 1,000,000,000top ，并使用或等价物来查看程序使用了多少内存。

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

1 - 天真的长乘法是O(N^2)，但有更好的算法具有更好的渐近性能。对于 2^2^96 范围内的数字，您应该查看Schönhage–Strassen 算法或Fürer 算法。一般来说，乘法算法的维基百科页面是开始阅读的好地方。

使用压缩大数的算术

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

如果您尝试将普通算术算法应用于压缩数字，则需要能够逐步解压缩输入、执行操作并压缩输出。这可行吗？好吧，这取决于细节。例如：

  • 要添加两个数字，您从最低有效端开始，并添加相应的位，进位并重复。完整的操作需要通过输入数字。如果您的压缩方案是（比如说）一个稀疏的位数组，那么这将起作用，但是如果您使用游程长度编码，那么您需要从最低有效位到最高有效位对运行进行编码。

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

  • 要除...你做N位移位和减去N次。和上面一样。

但是有两个问题：

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

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

那么有替代方案吗？

好吧，可能是的。如果您使用运行长度编码，则可以编写（例如）一个加法算法，将“运行”考虑在内。例如：

     10000000000000001
    +10000000000000001

  • 添加最左边的数字对

                    10

  • 添加零的匹配运行

      0000000000000010

  • 添加 MSB

    100000000000000010

然后你可以从中建立更复杂的操作。

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

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

总之：

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

  2. 值得怀疑的是，这在通用“大数字”库（如 GMP）中是一种可行的方法。我们在数字上下文中遇到的典型大数不能充分压缩......以一种有帮助的方式。如果压缩没有帮助，它可能会阻碍。

  3. 如果存在这样的库，这在特殊用途的“大数字”库中可能是可行的。在适当的情况下，压缩算法应该比普通的 bignum 算法具有更好的复杂性。

于 2013-06-30T00:41:03.100 回答
1

按照设计，是的。它会尝试存储和操作您提供的任何数字，尽管在许多情况下，与您类似的问题会变得不合理。

实际上，操作系统和计算机硬件设置了限制。

在最佳未压缩情况下，2^2^96 需要 2^96 位来表示。这仅相当于 9,904,000,000,000,000 太字节。您的计算机无法存储那么多数据。此外，最多只能索引大约 40 亿个数组，不足以管理这个巨大的数据堆。为了解决这些位中的每一个，我们需要一个由 40 亿个条目数组组成的 40 亿个条目数组的 40 亿个条目数组。我不完全确定这是否允许，因为总元素大于 40 亿。

无论如何，在 32 位 JVM 上，您的堆最大容量为 4 GB。请注意，即使您可以存储这么多位，并且以 4 GB/秒的速度进行操作，也需要 78,460,000,000 年。

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

于 2013-06-29T23:07:08.790 回答
0

mpn虽然在级别上没有限制，但an 的大小由 anmpz_t表示int，它在所有平台上都是 32 位类型（至少是 GMP 支持的平台）；请参阅GMP 手册中的Integer Internals。这意味着在 64 位平台上存在 2^37 位的限制（一个mpz_t整数将具有少于 2^31 个 64 = 2^6 位的分支）。

注意： 2012 年 4 月，Torbjörn Granlund 在 gmp-discuss list 中提到了 2^37 位的限制。

于 2020-06-23T08:25:59.110 回答