BigInt

BigInt module: arbitrary-precision integers.

Representation: BigInt(sign, digits) where sign : Bool — true = non-negative, false: negative digits : List(Int) — little-endian base-10000 digit list (least significant limb first) BigInt(true, Nil) represents zero.

Base 10000 is convenient: each limb stores 4 decimal digits, so to_string is straightforward without requiring integer logarithms.

Interface implementations: impl Eq(BigInt) — eq/2, == impl Ord(BigInt) — compare/2, < impl Show(BigInt) — show/1

Types

ptypeBigIntBigInt = BigInt(Bool, List(Int))#

Functions

fnabsabs(n : BigInt) : BigInt#

Returns the absolute value of a BigInt.

Examples

march> BigInt.to_string(BigInt.abs(BigInt.from_int(-123)))
"123"
march> BigInt.to_string(BigInt.abs(BigInt.from_int(123)))
"123"

fnaddadd(a : BigInt, b : BigInt) : BigInt#

Adds two BigInts. A result of zero is always non-negative.

Examples

march> BigInt.to_string(BigInt.add(BigInt.from_int(9999), BigInt.from_int(1)))
"10000"
march> BigInt.to_string(BigInt.add(BigInt.from_int(5), BigInt.from_int(-12)))
"-7"
march> BigInt.to_string(BigInt.add(BigInt.mul(BigInt.from_int(2000000000), BigInt.from_int(2000000000)), BigInt.one()))
"4000000000000000001"

fncomparecompare(a : BigInt, b : BigInt) : Int#

Compares two BigInts. Returns -1 (a < b), 0 (a == b), or 1 (a > b).

Examples

march> BigInt.compare(BigInt.from_int(-5), BigInt.from_int(3))
-1
march> BigInt.compare(BigInt.from_int(10000), BigInt.from_int(9999))
1
march> BigInt.compare(BigInt.zero(), BigInt.negate(BigInt.zero()))
0

fndivdiv(a : BigInt, b : BigInt) : BigInt#

Divides a by b, truncating toward zero: div(-17, 3) == -5, div(17, -3) == -5, div(-17, -3) == 5. Panics if b is zero.

Limitation: only single-limb divisors (|b| < 10000, one base-10000 limb) are supported in the current implementation. Any larger divisor panics with BigInt.div: multi-limb divisor not yet supported (a loud failure, not a silent wrong result), so callers must guard against it until long division lands. The dividend may be arbitrarily large.

Examples

march> BigInt.to_string(BigInt.div(BigInt.from_int(-17), BigInt.from_int(3)))
"-5"
march> BigInt.to_string(BigInt.div(BigInt.from_int(17), BigInt.from_int(-3)))
"-5"
march> BigInt.to_string(BigInt.div(BigInt.mul(BigInt.from_int(123456789), BigInt.from_int(987654321)), BigInt.from_int(9999)))
"12194482559519"

fneqeq(a : BigInt, b : BigInt) : Bool#

Returns true if a equals b (also available as ==).

Examples

march> BigInt.eq(BigInt.from_int(7), BigInt.add(BigInt.from_int(3), BigInt.from_int(4)))
true
march> BigInt.eq(BigInt.from_int(7), BigInt.from_int(-7))
false

fnfrom_intfrom_int(n : Int) : BigInt#

Converts a native Int to a BigInt. Negative values keep their sign.

Examples

march> BigInt.to_string(BigInt.from_int(1234567))
"1234567"
march> BigInt.to_string(BigInt.from_int(-42))
"-42"

fngtgt(a : BigInt, b : BigInt) : Bool#

Returns true if a > b.

Examples

march> BigInt.gt(BigInt.from_int(10000), BigInt.from_int(9999))
true
march> BigInt.gt(BigInt.from_int(-1), BigInt.zero())
false

fngtegte(a : BigInt, b : BigInt) : Bool#

Returns true if a >= b.

Examples

march> BigInt.gte(BigInt.zero(), BigInt.from_int(-3))
true
march> BigInt.gte(BigInt.from_int(-4), BigInt.from_int(-3))
false

fnis_negativeis_negative(n : BigInt) : Bool#

Returns true if the BigInt is negative (< 0). Zero is not negative.

Examples

march> BigInt.is_negative(BigInt.from_int(-1))
true
march> BigInt.is_negative(BigInt.zero())
false

fnis_positiveis_positive(n : BigInt) : Bool#

Returns true if the BigInt is positive (> 0). Zero is not positive.

Examples

march> BigInt.is_positive(BigInt.from_int(1))
true
march> BigInt.is_positive(BigInt.zero())
false

fnis_zerois_zero(n : BigInt) : Bool#

Returns true if the BigInt is zero.

Examples

march> BigInt.is_zero(BigInt.sub(BigInt.one(), BigInt.one()))
true
march> BigInt.is_zero(BigInt.one())
false

fnltlt(a : BigInt, b : BigInt) : Bool#

Returns true if a < b.

Examples

march> BigInt.lt(BigInt.from_int(-10), BigInt.from_int(-2))
true
march> BigInt.lt(BigInt.one(), BigInt.one())
false

fnltelte(a : BigInt, b : BigInt) : Bool#

Returns true if a <= b.

Examples

march> BigInt.lte(BigInt.one(), BigInt.one())
true
march> BigInt.lte(BigInt.from_int(2), BigInt.one())
false

fnmod_mod_(a : BigInt, b : BigInt) : BigInt#

Computes a mod b (truncated modulo: the result has the sign of a, or is zero). The identity a == div(a, b) * b + mod_(a, b) always holds. Panics if b is zero.

Limitation: only single-limb divisors (|b| < 10000) are supported. Any larger divisor panics with BigInt.mod: multi-limb divisor not yet supported.

Examples

march> BigInt.to_string(BigInt.mod_(BigInt.from_int(17), BigInt.from_int(3)))
"2"
march> BigInt.to_string(BigInt.mod_(BigInt.from_int(-17), BigInt.from_int(3)))
"-2"
march> BigInt.to_string(BigInt.mod_(BigInt.from_int(17), BigInt.from_int(-3)))
"2"

fnmulmul(a : BigInt, b : BigInt) : BigInt#

Multiplies two BigInts (schoolbook, O(n*m) in the number of base-10000 limbs). The product never overflows.

Examples

march> BigInt.to_string(BigInt.mul(BigInt.from_int(123456789), BigInt.from_int(987654321)))
"121932631112635269"
march> BigInt.to_string(BigInt.mul(BigInt.from_int(-25), BigInt.from_int(4)))
"-100"
march> BigInt.to_string(BigInt.mul(BigInt.from_int(-25), BigInt.zero()))
"0"

fnnegatenegate(a : BigInt) : BigInt#

Negates a BigInt. The negation of zero is zero.

Examples

march> BigInt.to_string(BigInt.negate(BigInt.from_int(15)))
"-15"
march> BigInt.to_string(BigInt.negate(BigInt.zero()))
"0"

fnoneone() : BigInt#

Returns BigInt one.

Examples

march> BigInt.to_string(BigInt.one())
"1"

fnsubsub(a : BigInt, b : BigInt) : BigInt#

Subtracts b from a.

Examples

march> BigInt.to_string(BigInt.sub(BigInt.from_int(5), BigInt.from_int(12)))
"-7"
march> BigInt.is_zero(BigInt.sub(BigInt.from_int(-3), BigInt.from_int(-3)))
true

fnto_stringto_string(n : BigInt) : String#

Converts a BigInt to its decimal string representation, with a leading - for negative values and "0" for zero.

The digits are stored in base 10^4 (little-endian), so each limb contributes 4 decimal characters (with leading zeros on all but the most-significant limb). Pieces are collected into a list and string_join-ed once at the end, making the routine O(number of limbs) rather than the quadratic behaviour of repeated ++.

Examples

march> BigInt.to_string(BigInt.from_int(100020003))
"100020003"
march> BigInt.to_string(BigInt.mul(BigInt.from_int(-1000000), BigInt.from_int(1000000)))
"-1000000000000"

fnzerozero() : BigInt#

Returns BigInt zero.

Examples

march> BigInt.to_string(BigInt.zero())
"0"
march> BigInt.is_zero(BigInt.zero())
true