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

Question

Rust 中 num 板条箱中 BigInt 或 BigUint 的大小没有限制吗？我看到在 Java 中，它的长度受整数 Integer.MAX_VALUE 的上限限制，因为它存储为 int.

的数组

我确实查看了它的文档，但无法真正从中推断出我的答案

A BigUint-typed value BigUint { data: vec!(a, b, c) } represents a number (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 会完成这项工作，无论您如何使用它。

理论上，自 the documentation says nothing about it (version 0.1.44) 以来，num 个大整数大小没有限制。但是，我们可以计算出一个具体的限制：

BigUint is a Vec<BigDigit>, and BigDigit is an u32. As far as I know, Rust does not define a max size for a Vec, but since ，BigDigit 又名 u32 的最大数量是：

MAX_LEN = isize::MAX / sizeof(u32)

根据这些信息，我们可以推断出当前实现中 num::BigUint（以及 num::BigInt）的最大值为：

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

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

这里是 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)

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

Is there a limit to the size of a BigInt or BigUint in Rust?