RU EN
GitHub

← Документация · nv-lang/nova-bignum

BigInt

BigInt — целое со знаком произвольной точности, модуль bignum.bigint. Как он соотносится с остальной семьёй bignum — см. overview.ru.md.

Представление

type Sign enum Neg | Zero | Pos

type BigInt value {
    sign Sign
    limbs []u32
}
  • Знак-модуль: знак живёт в отдельном поле Sign, модуль — в поле limbs (цифры числа по основанию 2³², младшая первая — каждый элемент хранит одну 32-битную «цифру»): little-endian разряды по основанию 2³², без ведущих нулевых лимбов.
  • Ноль каноничен: sign: Zero, limbs: [] — единственное представление нуля; каждая операция нормализует результат к нему.
  • Value-record на стеке: копия — тег enum Sign плюс slice-заголовок, примерно 24 байта; сами данные лимбов — на GC-куче и разделяются при копировании (иммутабельность гарантирует, что ни один alias не мутирует разделяемый буфер).
  • == структурное (равенство value-record, D328) и согласовано с @equal/@compare.

Построение

ro z = BigInt.zero()
ro o = BigInt.one()

ro a = 42.to_bigint()
ro b = "12345678901234567890".to_bigint()!!
  • BigInt.zero() / BigInt.one() — две константы.
  • T @to_bigint() для любого члена Ints (i8..i64, u8..u64, int, uint) — бесотказная, всегда точная.
  • i128 @to_bigint() — библиотечный 128-битный тип, тоже бесотказная.
  • str @to_bigint() — десятичная строка → Result[BigInt, ParseNumberError]; принимает опциональный ведущий +/-, отвергает всё, что не ASCII-цифра после знака.

Предикаты

assert(BigInt.zero().is_zero())
assert(!BigInt.one().is_zero())
assert(BigInt.one().is_one())
assert(((-1).to_bigint()).is_neg())
assert(42.to_bigint().is_even())

@is_zero(), @is_neg(), @is_pos(), @is_one(), @is_even(), @sign() -> Sign.

Сравнение

assert(42.to_bigint() == 42.to_bigint())
assert(42.to_bigint() != 43.to_bigint())
assert(BigInt.one() > BigInt.zero())
assert((-BigInt.one()) < BigInt.one())
assert(100.to_bigint().compare(50.to_bigint()) > 0)

@equal(other) стоит за ==/!=; @compare(other) -> int даёт полное знаковое упорядочивание -1/0/1 и стоит за </>.

Арифметика

ro a = 2.to_bigint()
ro b = 3.to_bigint()
assert(a + b == 5.to_bigint())
assert(a - b == (-1).to_bigint())
assert(-a == (-2).to_bigint())
assert(a.abs() == a)
assert(a * b == 6.to_bigint())

ro (q, r) = 100.to_bigint().div_rem(3.to_bigint())!!
assert(q == 33.to_bigint())
assert(r == 1.to_bigint())
  • +/-/унарный -/* десугарятся в @plus/@minus/@neg/@times соответственно; у @abs операторной формы нет. Все бесотказные и точные.
  • @div_rem(other) -> Result[(BigInt, BigInt), DivError] — единственный примитив деления; @div/@rem — тонкие обёртки над ним. Операторы / и % НЕ десугарятся в них — деление может отказать (деление на ноль), поэтому оно остаётся явным вызовом метода, возвращающим Result. Усечение к нулю, остаток несёт знак делимого (паритет int/C99/Rust).
  • @gcd(other) -> BigInt — бинарный алгоритм Евклида через @rem; результат всегда неотрицателен, gcd(0, 0) == 0.
  • @pow(n uint) -> BigInt — бинарное возведение в степень, n >= 0.
assert(2.to_bigint().pow(10) == 1024.to_bigint())
assert(48.to_bigint().gcd(36.to_bigint()) == 12.to_bigint())

Битовые операции

@shl(bits int) / @shr(bits int) — беззнаковый сдвиг модуля (знак сохраняется); @shr усекает к нулю, что совпадает с @div на степень двойки. @bit_length() -> int — значащие биты абсолютного значения (0 для нуля). @digits() -> int — количество десятичных цифр (V1: реализовано через @to_str()).

ro x = BigInt.one().shl(100)
assert(x.bit_length() == 101)
assert(x.shr(100) == BigInt.one())

Строковые конверсии

assert(42.to_bigint().to_str() == "42")
assert((-42).to_bigint().to_str() == "-42")

ro v = (12345678901234567890 as u64).to_bigint()
assert(v.to_str() == "12345678901234567890")

@to_str() -> str — каноничная десятичная запись, без ведущих нулей (кроме самого "0"), знак печатается только для отрицательных значений.

Конверсии обратно в фиксированные типы

assert(1234567890.to_bigint().to_int() == Some(1234567890))

@to_int() -> Option[int] и @to_i128() -> Option[i128] — Some, если значение помещается в диапазон приёмника, None при переполнении. Ни усекающего, ни wrapping-варианта в V1 нет — каждое сужение проверяется.

Умножение: Карацуба

Умножение использует алгоритм Карацубы, O(n^log₂3) ≈ O(n^1.585), с переключением на школьное O(n²) умножение ниже порога в 16 лимбов (разбиение ниже этого размера стоит дороже, чем экономит). Оба пути проверяются друг против друга на эквивалентность — см. src/bigint/mul_equiv_test.nv. Toom-3 — кандидат в V2, не реализован.

Деление: алгоритм Кнута D

Деление (@div_rem) реализует алгоритм Кнута D (TAOCP §4.3.1): нормализовать делитель так, чтобы у старшего лимба был установлен старший бит, догадаться о каждом разряде частного по двум старшим лимбам делителя, скорректировать догадку при заёме в пробном вычитании, затем денормализовать остаток. Однолимбовый делитель идёт по отдельному быстрому пути (обычное поразрядное длинное деление, нормализация не нужна).

ro a = "1427247692705959881058285969449495137370400945".to_bigint()!!
ro b = "1208925819614629174706189".to_bigint()!!
ro (q, r) = a.div_rem(b)!!

Ограничения

  • Все аллокации — на GC-куче; каждая операция создаёт новый BigInt вместо мутации на месте.
  • Мутирующих методов вида @add_assign/@mul_assign в V1 нет: копия разделяет буфер лимбов, мутация на месте испортила бы значение, на которое ссылается другая переменная — гарантия иммутабельности value-record сломалась бы. Buffer-reuse — задача V2.
  • modpow и битовые &/| (в отличие от сдвигов выше) в V1 нет.
  • Нет неявной коэрсии int → BigInt и нет суффиксной формы целочисленного литерала (например, 123456789012345678901n) — каждая конверсия — явный вызов @to_bigint().

Связанные документы

Править эту страницу ↗ Сообщить о проблеме ↗