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

Question

Rust 中 num crate 中的 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将完成这项工作，无论您如何使用它。

---

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

BigUint is a Vec<BigDigit> , 和 BigDigit is an u32 .据我所知，Rust 没有为 Vec 定义最大尺寸。 , 但由于 the maximum possible allocated size is isize::MAX , 最大数量 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 的方式，例如:

• 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)

The general formula of the sum of x^n is (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