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

Question

Is there no limit to the size of a BigInt or BigUint from the num crate in Rust? I see that in Java its length is bounded by the upper limit of an integer Integer.MAX_VALUE as it is stored as an array of int.

I did go through the documentation for it but could not really deduce my answer from

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 being defined as

pub const BASE: DoubleBigDigit = 1 << BITS

BITS in turn is 32

So is the BigInt being represented as (a + b * 64 + c * 64^2) internally?

Answer 1

TL;DR: the maximum number that can be represented is roughly:

3.079 x 10^22212093154093428519

I suppose that nothing useful needs such a big number to be represented. You can be certain that the num_bigint will do the job, whatever the usage you have with it.

---

In theory, there is no limit to the num big integers size since the documentation says nothing about it (version 0.1.44). However, there is a concrete limit that we can calculate:

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 the maximum possible allocated size is isize::MAX, the maximum number of BigDigit aka u32 is:

MAX_LEN = isize::MAX / sizeof(u32)

With this information, we can deduce that the maximum of a num::BigUint (and a num::BigInt as well) in the current implementation is:

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

To have this formula, we mimic the way we calculate u8::MAX, for example:

• bit::MAX is 1,
• the length is 8,
• so the maximum is (bit::MAX + 1) ^ 8 - 1 = 255

---

Here is the full demonstration from the formula given by the num documentation:

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

If we are taking the max value, a == b == c == u32::MAX. Let's name it a. Let's name big_digit::BASE b for convenience. So the max number is:

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

if we factorize, we get:

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). So, because n is MAX_LEN - 1, the result is:

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

We replace a and b with the right value, and the biggest representable number is:

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

u32::MAX is 2^32 - 1, so this can be simplified into:

2^32^MAX_LEN - 1