Есть ли ограничение на размер BigInt или BigUint в Rust? - PullRequest
Новая
       13

Есть ли ограничение на размер BigInt или BigUint в Rust?

0 голосов
/ 24 мая 2018

Нет ли ограничений на размер BigInt или BigUint от ящика num в Rust?Я вижу, что в Java его длина ограничена верхним пределом целого числа Integer.MAX_VALUE, поскольку он хранится в виде массива int.

. Я просмотрел документацию дляно не смог вывести мой ответ из

BigUint-типизированное значение BigUint {data: 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) внутри?

1 Ответ

0 голосов
/ 24 мая 2018

TL; DR : максимальное число, которое может быть представлено, примерно равно: 

3.079 x 10^22212093154093428519

Я полагаю, что ничто полезное не нуждается в таком большом числе, чтобы быть представленным.Вы можете быть уверены, что num_bigint выполнит эту работу, независимо от того, какое использование вы им пользуетесь.

Теоретически нет ограничения на размер больших целых чисел num, поскольку документация ничего не говорит об этом (версия 0.1.44) .Однако существует конкретный предел, который мы можем рассчитать:

BigUint - это Vec<BigDigit>, а BigDigit - это u32.Насколько я знаю, Rust не определяет максимальный размер для Vec, но, поскольку максимально возможный выделенный размер равен isize::MAX, максимальное число BigDigit aka 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 is 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
...