boost-multiprecision cpp_int 的最高限制是多少？

Question

我正在研究大半素数的因式分解。我正在研究 Java，但我也很想探索其他选项。我知道 C++ Boost 多精度支持大数。

我从 Boost 页面找到了以下信息：

typedef number<cpp_int_backend<128, 128, unsigned_magnitude, unchecked, void> >   uint128_t;
typedef number<cpp_int_backend<256, 256, unsigned_magnitude, unchecked, void> >   uint256_t;
typedef number<cpp_int_backend<512, 512, unsigned_magnitude, unchecked, void> >   uint512_t;
typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, unchecked, void> > uint1024_t;

我的问题是，cpp_int类型的最大数量限制是多少？在 Java 中，BigInteger 最多支持 2^Integer.MAX_VALUE.

谢谢。

Answer 1

`cpp_int` 没有[理论]最大值

请务必记住，在 Java 中，值的最大大小受到 Java 虚拟机表示值的物理限制的限制。在底层实现中，Java（可能）用这样的东西实现 BigInteger：

public class BigInteger {
    private long[] bits;//limited by the maximum size of an array in Java
    /*...*/
}

^{^{免责声明：我不知道他们是否使用 long[] 或 int[] 来存储位。}}

类似地，在 C++ 中，cpp_int 是，一旦你刮掉抽象，用非常相似的结构实现：

class boost::multiprecision::cpp_int {
    uint64_t * bits;
    uint64_t * end; //Points to the element-after-the-last in bits
    /*...*/
};

^{^{再次免责声明：他们可能做的事情比这更聪明。}}

Java 的理论限制是 JVM 在 Integer.MAX_VALUE 处对数组大小设置了硬上限，因为数组使用 int 而不是 [=19] 进行索引=]. C++ 可以直接使用指针，所以 C++ 中 cpp_int 的最大大小与指针可以寻址的最大内存范围成正比——在 64 位架构中是 usually-but-not-always™ 2⁶⁴-1;或者说，cpp_int的最大值是2^2⁶⁴-1-1，give-or-take一个阶数量级取决于他们如何实现标志。

在支持更大指针（或可以寻址更大内存范围的指针）的环境中，最大值可能更大。

实际上，cpp_int（以及 Java 的 BigInteger）的最大值是运行时环境允许的内存量的实际限制分配。

boost-multiprecision cpp_int 的最高限制是多少？

What is the highest limit for boost-multiprecision cpp_int?

c++

biginteger