Standard library · Numbers

num/bigint

Imported as import "num/bigint" as bigint, its names are then bigint.…. Every signature below is the one the checker infers.

Integers of any size, written in Rill.

A Big is a sign and a buffer of limbs in base 1,000,000,000, least significant first — nine decimal digits a limb, so a product of two limbs fits an Int with room for the carry, and writing one out is writing its limbs. Every value is normalized: no leading zero limbs, and zero is never negative, so equal numbers are equal buffers.

Addition and subtraction are linear, multiplication is the schoolbook quadratic, and division finds each quotient limb by binary search over products — fine for hundreds of digits, slow for a hundred thousand.

n = bigint.pow(bigint.from_int(2), 100)?
n                                                     # => 1267650600228229401496703205376
f = bigint.factorial(30)
(q, r) = bigint.divmod(f, bigint.parse("1000000007")?)?
bigint.add(q, r)                                      # => 265252857955421162309834

Types

Big

• Big(negative: Bool, limbs: Buf(Int))

Implementations

• impl Show(Big)
• impl Ord(Big)

Functions

fn zero() -> Big

bigint.zero()   # => 0

fn is_zero(b: Big) -> Bool

bigint.is_zero(bigint.sub(bigint.from_int(3), bigint.from_int(3)))   # => true

fn from_int(n: Int) -> Big

bigint.from_int(-42)   # => -42

fn as_int(b: Big) -> Option(Int)

The Int this is, or None past its range.

bigint.as_int(bigint.from_int(42))                        # => Some(42)
bigint.as_int(bigint.pow(bigint.from_int(10), 30)?)           # => None

fn neg(b: Big) -> Big

bigint.neg(bigint.from_int(5))   # => -5

fn abs_of(b: Big) -> Big

bigint.abs_of(bigint.from_int(-5))   # => 5

fn sign(b: Big) -> Int

bigint.sign(bigint.from_int(-5))   # => -1
bigint.sign(bigint.zero())         # => 0

fn cmp(a: Big, b: Big) -> Int

Negative, zero or positive as a is less than, equal to, or greater than b.

bigint.cmp(bigint.from_int(2), bigint.from_int(3))   # => -1

fn eq(a: Big, b: Big) -> Bool

bigint.eq(bigint.parse("007")?, bigint.from_int(7))   # => true

fn add(a: Big, b: Big) -> Big

bigint.add(bigint.parse("999999999999999999")?, bigint.from_int(1))   # => 1000000000000000000

fn sub(a: Big, b: Big) -> Big

bigint.sub(bigint.from_int(1), bigint.from_int(3))   # => -2

fn mul(a: Big, b: Big) -> Big

bigint.mul(bigint.parse("123456789012")?, bigint.parse("987654321098")?)   # => 121932631136585886175176

fn pow(b: Big, n: Int) -> Result(Big, Str)

b to the nth, by squaring; n below zero is an error, as an integer power is.

bigint.pow(bigint.from_int(3), 40)   # => Ok(12157665459056928801)
bigint.pow(bigint.from_int(3), -1)   # => Err(a negative power is not an integer)

fn factorial(n: Int) -> Big

bigint.factorial(25)   # => 15511210043330985984000000

fn divmod(a: Big, b: Big) -> Result((Big, Big), Str)

The quotient rounded toward zero and the remainder with the sign of a, as / and % on Int have them; Err on a zero divisor.

bigint.divmod(bigint.from_int(-7), bigint.from_int(2))   # => Ok((-3, -1))
bigint.divmod(bigint.from_int(1), bigint.zero())        # => Err(division by zero)

fn div(a: Big, b: Big) -> Result(Big, Str)

bigint.div(bigint.parse("1000000000000000000000")?, bigint.from_int(7))   # => Ok(142857142857142857142)

fn rem(a: Big, b: Big) -> Result(Big, Str)

bigint.rem(bigint.parse("1000000000000000000000")?, bigint.from_int(7))   # => Ok(6)

fn text(b: Big) -> Str

bigint.text(bigint.from_int(-1234567890123))   # => -1234567890123

fn parse(s: Str) -> Result(Big, Str)

Digits, with a - or + in front if wanted.

bigint.parse("-12345678901234567890")   # => Ok(-12345678901234567890)
bigint.parse("12x")                     # => Err(`12x` is not an integer)

Tests

• test_text_and_ints
• test_arithmetic
• test_division