boost-multi precision 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没有[理论]最大值

\n

重要的是要记住，在 Java 中，值的最大大小受到 Java 虚拟机表示值的物理限制的约束。在底层实现中，Java（可能）是BigInteger这样实现的：

\n

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

\n

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

\n

类似地，在 C++ 中，cpp_int一旦你去掉了抽象，就可以使用非常相似的结构来实现：

\n

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

\n

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

\n

对 Java 造成理论上的限制的是，JVM 对数组大小设置了硬性上限，Integer.MAX_VALUE因为数组是用int而非进行索引的long。C++ 可以直接使用指针，因此 C++ 中的最大大小与cpp_int指针可以寻址的最大内存范围\xe2\x80\x94 成正比，在 64 位体系结构中通常但不总是\xe2\x84\xa2 2 ⁶⁴ -1；或者换句话说， 的最大值cpp_int是 2 ^{2 64 -1} -1，根据他们如何实现符号来调整或调整一个数量级。

\n

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

\n

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

\n