Rust中的BigInt或BigUint的大小是否有限制？

Question

有没有限制的大小BigInt或BigUint从num鲁斯特箱子？我看到在Java中,它的长度受整数上限的限制,Integer.MAX_VALUE因为它存储为数组int.

我确实通过了它的文档,但无法真正推断出我的答案

甲BigUint类型的值BigUint {数据:VEC(A,B,C)}表示数(A + B*big_digit :: BASE + C*big_digit :: BASE ^ 2).

big_digit::BASE 被定义为

pub const BASE: DoubleBigDigit = 1 << BITS

BITS 反过来是32

那么BigInt是否在(a + b * 64 + c * 64^2)内部表现？

Answer 1

TL; DR:可以表示的最大数量大致为:

3.079 x 10^22212093154093428519

我想没有什么有用的东西需要这么大的数字来代表.你可以确定num_bigint无论你对它有什么用处,它都能完成这项工作.

从理论上讲,num大整数的大小没有限制,因为文档没有说明它(版本0.1.44).但是,我们可以计算出具体的限制:

BigUint是一个Vec<BigDigit>,BigDigit是一个u32.据我所知,锈不定义为一个最大规模Vec,但由于最大的可能分配的大小isize::MAX,最大数量BigDigit又名u32为:

MAX_LEN = isize::MAX / sizeof(u32)

有了这些信息,我们可以推断出当前实现中a num::BigUint(和a num::BigInt)的最大值是:

(u32::MAX + 1) ^ MAX_LEN - 1 = 2^32^MAX_LEN - 1

为了得到这个公式,我们模仿我们计算的方式u8::MAX,例如:

• bit::MAX是的1,
• 长度是8,
• 所以最大值是 (bit::MAX + 1) ^ 8 - 1 = 255

以下是num文档给出的公式的完整演示:

a + b * big_digit::BASE + c * big_digit::BASE^2 + ...

如果我们取最大值,a == b == c == u32::MAX.我们来命名吧a.我们big_digit::BASE b为方便起见.所以最大数量是:

sum(a * b^n) where n is from 0 to (MAX_LEN - 1)

如果我们分解,我们得到:

a * sum(b^n) where n is from 0 to (MAX_LEN - 1)

总和的一般公式x^n是(x^(n + 1) - 1) / (x - 1).所以,因为n是MAX_LEN - 1,结果是:

a * (b^(MAX_LEN - 1 + 1) - 1) / (b - 1)

我们用正确的值替换a和b,最大可表示的数字是:

u32::MAX * (2^32^MAX_LEN - 1) / (2^32 - 1)

u32::MAX是的2^32 - 1,所以这可以简化为:

2^32^MAX_LEN - 1