Standard library · Numbers and collections

bigint

Whole numbers of unlimited size: large factorials, cryptography, and any arithmetic that will not fit in 64 bits.

import bigint

An i64 stops at about 9.2 × 1018 and wraps around without warning. bigint.Int is a whole number whose size is limited only by memory: use it for factorials and combinatorics, exact counters that can grow without bound, token amounts in their smallest unit, and number theory such as modular exponentiation. For money with a fixed number of decimal places use decimal, and for real keys and signatures use crypto.

A number is a sign and a vector of 32-bit limbs. Multiplication is the schoolbook method and conversion to text divides repeatedly, so numbers of a few thousand digits are quick and numbers of a million digits are slow.

Most functions return a new number and leave their arguments alone. The ones whose names end in To, From or By, such as AddTo, store the result in their first argument and free its old value for you. They still allocate the new value, so they are not faster; what they save is the bookkeeping of freeing every intermediate result. Release a number you no longer need with Free.

What people get wrong:

  • Copying with =. b := a copies only the header, so both names share one set of limbs, and the next in-place call on b frees the memory a still points to. Use Clone for a second, independent number.
  • Dividing by zero. Div, Rem, Mod and ModExp do not stop the program; they return 0. When the divisor can be zero, use DivMod, which returns false.
  • Expecting an error for impossible input. A negative exponent in Pow, the square root of a negative number and the factorial of a negative number all return 0, and ToStrBase with a base outside 2 to 36 returns empty text.

Past the end of i64

The 93rd Fibonacci number is the first one that does not fit in an i64; with ordinary integers it would wrap around to a negative value without warning. With bigint.Int the loop just keeps going. ToInt converts back and tells you, through its bool argument, whether the value fitted, so you can move to plain integers when the numbers are small again.

bigint-guide-fibonacci.salam
import bigint
import str

func main:
    mut a := bigint.Zero()
    mut b := bigint.One()
    repeat 1 to 300 in n:
        next := bigint.Add(a, b)
        bigint.Free(a)
        a = b
        b = next
        if n == 92 or n == 93:
            mut fits := false
            v := bigint.ToInt(a, fits)
            println "F(" + str.FromInt(n) + ") =", bigint.ToStr(a), "fits in i64:", fits, v
        end
    end
    text := bigint.ToStr(a)
    println "F(300) has", text.Len(), "digits"
    println text
    bigint.Free(a)
    bigint.Free(b)
end
OutputF(92) = 7540113804746346429 fits in i64: true 7540113804746346429 F(93) = 12200160415121876738 fits in i64: false 0 F(300) has 63 digits 222232244629420445529739893461909967206666939096499764990979600

Each Add returns a new number, so the loop frees the value it no longer needs before it moves the names along. Without the Free calls the program would still be correct, but it would keep every intermediate number in memory.

Updating one number in a loop

A loop that updates one number with Add has to free the old value on every step, as the Fibonacci loop above does. MulIntBy, AddTo, ShlBy and the other functions named with To, From or By do that for you: they put the result into their first argument and free what was there. Build the result in one variable and free it once at the end.

bigint-guide-inplace.salam
import bigint

func main:
    mut product := bigint.One()
    defer bigint.Free(product)
    repeat 1 to 50 in i:
        bigint.MulIntBy(product, i as i64)
    end
    mut check := bigint.Factorial(50)
    defer bigint.Free(check)
    println "50! =", bigint.ToStr(product)
    println "same as Factorial(50):", bigint.Equals(product, check)
    mut total := bigint.Zero()
    defer bigint.Free(total)
    mut power := bigint.One()
    defer bigint.Free(power)
    repeat 64:
        bigint.AddTo(total, power)
        bigint.ShlBy(power, 1)
    end
    println "1 + 2 + 4 + ... + 2^63 =", bigint.ToStr(total)
    println "that is 2^64 - 1:", bigint.Equals(total, bigint.SubInt(power, 1))
end
Output50! = 30414093201713378043612608166064768844377641568960512000000000000 same as Factorial(50): true 1 + 2 + 4 + ... + 2^63 = 18446744073709551615 that is 2^64 - 1: true

Copies and snapshots

To keep an old value while you change the number, take a copy with Clone. A plain opening := balance would not work: both names would share the same limbs, and the first AddIntTo would free them under opening, which then prints garbage. Each clone is its own allocation and needs its own Free.

bigint-guide-copy.salam
import bigint

func main:
    mut ok := false
    mut balance := bigint.Parse("900000000000000000000", ok)
    mut opening := bigint.Clone(balance)
    defer bigint.Free(balance)
    defer bigint.Free(opening)
    bigint.AddIntTo(balance, 250 as i64)
    bigint.MulIntBy(balance, 2 as i64)
    println "opening:", bigint.ToStr(opening)
    println "now:    ", bigint.ToStr(balance)
    mut gain := bigint.Sub(balance, opening)
    defer bigint.Free(gain)
    println "gain:   ", bigint.ToStr(gain)
end
Outputopening: 900000000000000000000 now: 1800000000000000000500 gain: 900000000000000000500

Digits of very large numbers

ToStr gives the decimal text, so its length is the number of digits. DivModInt divides by an ordinary integer and puts the remainder into an i64, which is the way to walk through the digits one by one, here to add them up. TrailingZeros counts zero bits, not decimal zeros.

bigint-guide-digits.salam
import bigint

func digit_sum(x: bigint.Int): i64:
    mut rest := bigint.Clone(x)
    defer bigint.Free(rest)
    mut sum := 0 as i64
    until bigint.IsZero(rest) == false:
        mut d := 0 as i64
        q := bigint.DivModInt(rest, 10, d)
        bigint.Free(rest)
        rest = q
        sum += d
    end
    ret sum
end

func main:
    mut p := bigint.Pow(bigint.FromInt(2), 1000)
    mut f := bigint.Factorial(100)
    defer bigint.Free(p)
    defer bigint.Free(f)
    println "2^1000 has", bigint.ToStr(p).Len(), "digits, digit sum", digit_sum(p)
    println "100! has", bigint.ToStr(f).Len(), "digits, digit sum", digit_sum(f)
    println "100! ends in", bigint.TrailingZeros(f), "zero bits"
end
Output2^1000 has 302 digits, digit sum 1366 100! has 158 digits, digit sum 648 100! ends in 97 zero bits

Reading and printing in other bases

Parse reads decimal text and reports through its bool argument whether the text was a whole number; an empty string, a stray letter or a trailing space fails. Leading spaces, a sign, Persian digits and _ between digits (1_000_000) are accepted. With base 0, ParseBase reads a 0x, 0b or 0o prefix and falls back to decimal. ParseBase and ToStrBase handle bases from 2 to 36, and ToHex is the usual form for keys and hashes. ToIntClamped gives the largest or smallest i64 when the value is out of range.

bigint-guide-parse.salam
import bigint

func main:
    inputs := ["340282366920938463463374607431768211455", "-12345678901234567890", "12a4", ""]
    each s in inputs:
        mut ok := false
        mut n := bigint.Parse(s, ok)
        if ok:
            println s, "->", bigint.BitLen(n), "bits, sign", bigint.Sign(n)
        else:
            println "[" + s + "] is not a whole number"
        end
        bigint.Free(n)
    end
    mut ok := false
    mut key := bigint.ParseBase("deadbeefcafebabe0123456789", 16, ok)
    println ok, bigint.ToStr(key)
    println "base 36:", bigint.ToStrBase(key, 36)
    println "back to hex:", bigint.ToHex(key)
    println "clamped to i64:", bigint.ToIntClamped(key)
    bigint.Free(key)
end
Output340282366920938463463374607431768211455 -> 128 bits, sign 1 -12345678901234567890 -> 64 bits, sign -1 [12a4] is not a whole number [] is not a whole number true 17642423813161689323077271644041 base 36: 1biglrj84lzg25oox7rex back to hex: deadbeefcafebabe0123456789 clamped to i64: 9223372036854775807

Division, remainders and zero

There are three ways to divide, and they differ only for negative numbers. Div and Rem round towards zero, as C and Go do. FloorDiv and FloorMod round down, as Python does, so the remainder takes the sign of the divisor. Mod and ModInt always give a remainder from 0 up to the divisor, which is what modular arithmetic and a day-of-week calculation want. DivMod gives the quotient and the remainder from one division, and its bool is the only way to notice a zero divisor.

bigint-guide-division.salam
import bigint

func show(label: str, x: bigint.Int):
    println label, bigint.ToStr(x)
end

func main:
    mut ok := false
    mut pool := bigint.Parse("1_250_000_000_000_000_000_000", ok)
    defer bigint.Free(pool)
    mut winners := bigint.FromInt(7)
    defer bigint.Free(winners)
    mut share := bigint.Zero()
    mut dust := bigint.Zero()
    defer bigint.Free(share)
    defer bigint.Free(dust)
    if bigint.DivMod(pool, winners, share, dust):
        show("each winner gets:", share)
        show("left in the pool:", dust)
    end
    mut nobody := bigint.Zero()
    defer bigint.Free(nobody)
    if bigint.DivMod(pool, nobody, share, dust) == false:
        println "no winners: DivMod returned false"
    end
    mut silent := bigint.Div(pool, nobody)
    defer bigint.Free(silent)
    show("Div by zero quietly gives", silent)
    mut debt := bigint.FromInt(-10)
    mut days := bigint.FromInt(3)
    defer bigint.Free(debt)
    defer bigint.Free(days)
    mut t := bigint.Div(debt, days)
    mut m := bigint.Rem(debt, days)
    println "Div, Rem:", bigint.ToStr(t), bigint.ToStr(m)
    bigint.Free(t)
    bigint.Free(m)
    t = bigint.FloorDiv(debt, days)
    m = bigint.FloorMod(debt, days)
    println "FloorDiv, FloorMod:", bigint.ToStr(t), bigint.ToStr(m)
    bigint.Free(t)
    bigint.Free(m)
    println "ModInt:", bigint.ModInt(debt, 3)
end
Outputeach winner gets: 178571428571428571428 left in the pool: 4 no winners: DivMod returned false Div by zero quietly gives 0 Div, Rem: -3 -1 FloorDiv, FloorMod: -4 2 ModInt: 2

Modular arithmetic: a toy RSA

Public key cryptography is built on ModExp, ModInverse and Gcd. The program below makes an RSA key from two small primes, encrypts a number with the public exponent and decrypts it with the private one. ModInverse fails, through its bool, when the two numbers share a factor.

bigint-guide-rsa.salam
import bigint

func main:
    p := bigint.FromInt(1000000007)
    q := bigint.FromInt(998244353)
    n := bigint.Mul(p, q)
    phi := bigint.Mul(bigint.SubInt(p, 1), bigint.SubInt(q, 1))
    e := bigint.FromInt(65537)
    println "public key n:", bigint.ToStr(n), "e:", bigint.ToStr(e)
    println "gcd(e, phi):", bigint.ToStr(bigint.Gcd(e, phi))
    mut ok := false
    d := bigint.ModInverse(e, phi, ok)
    if not ok:
        println "e has no inverse, pick another e"
        ret 1
    end
    println "private exponent d:", bigint.ToStr(d)
    message := bigint.FromInt(424242424242)
    secret := bigint.ModExp(message, e, n)
    back := bigint.ModExp(secret, d, n)
    println "message:  ", bigint.ToStr(message)
    println "encrypted:", bigint.ToStr(secret)
    println "decrypted:", bigint.ToStr(back)
    println "round trip:", bigint.Equals(message, back)
    ret 0
end
Outputpublic key n: 998244359987710471 e: 65537 gcd(e, phi): 1 private exponent d: 78519762354634753 message: 424242424242 encrypted: 539629950315152176 decrypted: 424242424242 round trip: true

This is for learning how the arithmetic works. Real RSA needs primes of more than a thousand bits, random padding and constant time code; for real keys and signatures use crypto.

JobUse
Arithmetic that returns a new numberAdd, Sub, Mul, Div, Pow
A long loop that updates one numberAddTo, MulBy, MulIntBy, ShlBy
A second, independent numberClone
Division that can see a zero divisorDivMod, FloorDivMod
ComparisonsCmp, Equals, Less, Greater
Modular arithmeticModExp, ModInverse, Mod
Text in and outParse, ParseBase, ToStr, ToHex
Back to a normal integerToInt, ToIntClamped

Types

Int

struct Int
A whole number of any size. Build one with a function such as FromInt or Parse. Assigning it to another name shares its limbs; use Clone for a copy.
NameTypeDescription
negbool = falseTrue when the number is negative.
magVectorThe absolute value, as 32-bit limbs from least to most significant.
bigint-Int.salam
import bigint

func main:
    mut a := bigint.FromInt(123456789)
    mut b := bigint.Pow(bigint.FromInt(2), 100)
    defer a.Free()
    defer b.Free()
    println b.ToStr()
    println a.is_zero(), a.sign(), a.is_odd(), a.is_even()
    println b.bit_len(), b.limb_count()
    c := a.Clone()
    println c.ToStr()
end
Output1267650600228229401496703205376 false 1 true false 101 4 123456789

Free

func Free()

free

func free()
Releases the number's memory.

The example for this item is shown with the ones above: bigint-Int.salam

IsZero

func IsZero(): bool

is_zero

func is_zero(): bool
True when the number is zero.

The example for this item is shown with the ones above: bigint-Int.salam

Sign

func Sign(): int

sign

func sign(): int
The sign: minus one, zero or one.

The example for this item is shown with the ones above: bigint-Int.salam

IsOdd

func IsOdd(): bool

is_odd

func is_odd(): bool
True when the number is odd.

The example for this item is shown with the ones above: bigint-Int.salam

IsEven

func IsEven(): bool

is_even

func is_even(): bool
True when the number is even.

The example for this item is shown with the ones above: bigint-Int.salam

BitLen

func BitLen(): int

bit_len

func bit_len(): int
How many bits the absolute value needs.

The example for this item is shown with the ones above: bigint-Int.salam

LimbCount

func LimbCount(): int

limb_count

func limb_count(): int
How many 32-bit limbs the number occupies.

The example for this item is shown with the ones above: bigint-Int.salam

Clone

func Clone(): Int

clone

func clone(): Int
An independent copy of the number.

The example for this item is shown with the ones above: bigint-Int.salam

ToStr

func ToStr(): str

to_str

func to_str(): str
The number as decimal text.

The example for this item is shown with the ones above: bigint-Int.salam

Functions

ToStr

func ToStr(x: Int): str
The number as decimal text.
bigint-Add.salam
import bigint

func main:
    a := bigint.FromInt(9000000000000000000)
    b := bigint.FromUint(18000000000000000000 as u64)
    println bigint.ToStr(bigint.Add(a, b))
    println bigint.ToStr(bigint.Sub(a, b))
    println bigint.ToStr(bigint.Mul(a, b))
    println bigint.ToStr(bigint.Sqr(a))
    println bigint.ToStr(bigint.AddInt(a, 1)), bigint.ToStr(bigint.SubInt(a, 1)), bigint.ToStr(bigint.MulInt(a, 2))
    println bigint.ToStr(bigint.Neg(a)), bigint.ToStr(bigint.Abs(bigint.Neg(a)))
    println bigint.ToStr(bigint.Shl(bigint.One(), 70)), bigint.ToStr(bigint.Shr(a, 60))
    println bigint.ToStr(bigint.Zero()), bigint.ToStr(bigint.Pow10(20))
end
Output27000000000000000000 -9000000000000000000 162000000000000000000000000000000000000 81000000000000000000000000000000000000 9000000000000000001 8999999999999999999 18000000000000000000 -9000000000000000000 9000000000000000000 1180591620717411303424 7 0 100000000000000000000

ToStrBase

func ToStrBase(x: Int, base: int): str
The number as text in a base from 2 to 36, with lower case letters and a leading - for a negative number. Another base gives empty text.
bigint-Parse.salam
import bigint

func main:
    mut ok := false
    n := bigint.Parse("123456789012345678901234567890", ok)
    println ok, bigint.ToStr(n)
    h := bigint.ParseBase("ff", 16, ok)
    println ok, bigint.ToStr(h), bigint.ToStrBase(h, 2), bigint.ToHex(n)
    println bigint.ToStr(bigint.ParseOr("xyz", 10))
    mut fits := false
    v := bigint.ToInt(h, fits)
    println v, fits
    println bigint.ToIntClamped(n), bigint.ToFloat(n)
end
Outputtrue 123456789012345678901234567890 true 255 11111111 18ee90ff6c373e0ee4e3f0ad2 0 255 true 9223372036854775807 1.2345678901234568e+29

ToHex

func ToHex(x: Int): str
The number in lower case base sixteen, with no 0x prefix.

The example for this item is shown with the ones above: bigint-Parse.salam

Parse

func Parse(s: str, ok &: bool): Int
Turns decimal text into a big number. Leading spaces, a sign, Persian or Arabic digits and _ between digits are accepted. When the text is not a valid number, ok turns false and the result is 0.

The example for this item is shown with the ones above: bigint-Parse.salam

ParseBase

func ParseBase(s: str, base: int, ok &: bool): Int
Turns text in a base from 2 to 36 into a number. Base 0 reads a 0x, 0b or 0o prefix and otherwise means base 10.

The example for this item is shown with the ones above: bigint-Parse.salam

ParseOr

func ParseOr(s: str, base: int): Int
Parses text in the given base, returning zero when it cannot; use it only when 0 is a safe default.

The example for this item is shown with the ones above: bigint-Parse.salam

ToInt

func ToInt(x: Int, ok &: bool): i64
Converts the number to an i64; when it does not fit, ok turns false and the result is 0.

The example for this item is shown with the ones above: bigint-Parse.salam

ToIntClamped

func ToIntClamped(x: Int): i64
Converts the number to an i64, giving the largest or smallest possible value when it does not fit.

The example for this item is shown with the ones above: bigint-Parse.salam

ToFloat

func ToFloat(x: Int): f64
Converts the number to the nearest f64; the least significant digits may be lost.

The example for this item is shown with the ones above: bigint-Parse.salam

ByteLen

func ByteLen(x: Int): int
How many bytes the absolute value needs.
bigint-Bytes.salam
import bigint
import mem

func main:
    n := bigint.FromInt(65536)
    size := bigint.ByteLen(n)
    println size
    buf := mem.Allocate(size as u64)
    println bigint.ToBytes(n, buf, size)
    back := bigint.FromBytes(buf, size)
    println bigint.ToStr(back)
    mem.Free(buf)
end
Output3 true 65536

FromBytes

func FromBytes(p: void*, n: int): Int
Builds the number from n bytes in memory, most significant first.

The example for this item is shown with the ones above: bigint-Bytes.salam

ToBytes

func ToBytes(x: Int, out: void*, n: int): bool
Writes the absolute value into n bytes of memory, most significant first; it returns false when it does not fit.

The example for this item is shown with the ones above: bigint-Bytes.salam

Zero

func Zero(): Int
The number zero.

The example for this item is shown with the ones above: bigint-Add.salam

One

func One(): Int
The number one.

The example for this item is shown with the ones above: bigint-Add.salam

FromInt

func FromInt(v: i64): Int
Builds a big number from an i64.

The example for this item is shown with the ones above: bigint-Int.salam

FromUint

func FromUint(v: u64): Int
Builds a big number from a u64.

The example for this item is shown with the ones above: bigint-Add.salam

Clone

func Clone(x: Int): Int
An independent copy of the number.
bigint-Cmp.salam
import bigint

func main:
    a := bigint.FromInt(5)
    b := bigint.FromInt(-9)
    println bigint.Cmp(a, b), bigint.CmpAbs(a, b)
    println bigint.Equals(a, a), bigint.Less(a, b), bigint.Greater(a, b)
    println bigint.ToStr(bigint.Min(a, b)), bigint.ToStr(bigint.Max(a, b))
    println bigint.EqualsInt(a, 5), bigint.IsZero(a), bigint.Sign(b)
    println bigint.IsOdd(a), bigint.IsEven(a), bigint.BitLen(a), bigint.Bit(a, 1)
    c := bigint.Clone(b)
    println bigint.ToStr(c)
end
Output1 -1 true false true -9 5 true false -1 true false 3 0 -9

Free

func Free(x &: Int)
Releases the number's memory.
bigint-AddTo.salam
import bigint

func main:
    mut acc := bigint.Zero()
    defer bigint.Free(acc)
    bigint.SetInt(acc, 10)
    bigint.AddTo(acc, bigint.FromInt(5))
    bigint.SubFrom(acc, bigint.FromInt(3))
    bigint.MulBy(acc, bigint.FromInt(4))
    println bigint.ToStr(acc)
    bigint.AddIntTo(acc, 2)
    bigint.MulIntBy(acc, 10)
    println bigint.ToStr(acc)
    bigint.NegateIn(acc)
    bigint.ShlBy(acc, 1)
    println bigint.ToStr(acc)
    bigint.ShrBy(acc, 2)
    println bigint.ToStr(acc)
    bigint.Set(acc, bigint.FromInt(7))
    println bigint.ToStr(acc)
end
Output48 500 -1000 -250 7

IsZero

func IsZero(x: Int): bool
True when the number is zero.

The example for this item is shown with the ones above: bigint-Cmp.salam

Sign

func Sign(x: Int): int
The sign: minus one, zero or one.

The example for this item is shown with the ones above: bigint-Cmp.salam

BitLen

func BitLen(x: Int): int
How many bits the absolute value needs.

The example for this item is shown with the ones above: bigint-Cmp.salam

Bit

func Bit(x: Int, i: int): int
Bit number i of the absolute value, zero or one.

The example for this item is shown with the ones above: bigint-Cmp.salam

IsOdd

func IsOdd(x: Int): bool
True when the number is odd.

The example for this item is shown with the ones above: bigint-Cmp.salam

IsEven

func IsEven(x: Int): bool
True when the number is even.

The example for this item is shown with the ones above: bigint-Cmp.salam

Cmp

func Cmp(a: Int, b: Int): int
Compares two numbers: minus one, zero or one.

The example for this item is shown with the ones above: bigint-Cmp.salam

CmpAbs

func CmpAbs(a: Int, b: Int): int
Compares the absolute values of two numbers.

The example for this item is shown with the ones above: bigint-Cmp.salam

Equals

func Equals(a: Int, b: Int): bool
True when the two numbers are equal.

The example for this item is shown with the ones above: bigint-Cmp.salam

Less

func Less(a: Int, b: Int): bool
True when the first is smaller.

The example for this item is shown with the ones above: bigint-Cmp.salam

Greater

func Greater(a: Int, b: Int): bool
True when the first is larger.

The example for this item is shown with the ones above: bigint-Cmp.salam

Min

func Min(a: Int, b: Int): Int
The smaller of two numbers.

The example for this item is shown with the ones above: bigint-Cmp.salam

Max

func Max(a: Int, b: Int): Int
The larger of two numbers.

The example for this item is shown with the ones above: bigint-Cmp.salam

EqualsInt

func EqualsInt(a: Int, v: i64): bool
True when the big number equals an i64.

The example for this item is shown with the ones above: bigint-Cmp.salam

Neg

func Neg(x: Int): Int
The number with its sign reversed.

The example for this item is shown with the ones above: bigint-Add.salam

Abs

func Abs(x: Int): Int
The absolute value.

The example for this item is shown with the ones above: bigint-Add.salam

Add

func Add(a: Int, b: Int): Int
The sum of two numbers.

The example for this item is shown with the ones above: bigint-Add.salam

Sub

func Sub(a: Int, b: Int): Int
The difference of two numbers.

The example for this item is shown with the ones above: bigint-Add.salam

Mul

func Mul(a: Int, b: Int): Int
The product of two numbers.

The example for this item is shown with the ones above: bigint-Add.salam

Sqr

func Sqr(x: Int): Int
The number squared, which is faster than multiplying it by itself.

The example for this item is shown with the ones above: bigint-Add.salam

AddInt

func AddInt(a: Int, v: i64): Int
Adds an ordinary whole number.

The example for this item is shown with the ones above: bigint-Add.salam

SubInt

func SubInt(a: Int, v: i64): Int
Subtracts an ordinary whole number.

The example for this item is shown with the ones above: bigint-Add.salam

MulInt

func MulInt(a: Int, v: i64): Int
Multiplies by an ordinary whole number.

The example for this item is shown with the ones above: bigint-Add.salam

Shl

func Shl(x: Int, k: int): Int
Shifts left by k bits, that is, multiplies by 2 to the power k.

The example for this item is shown with the ones above: bigint-Add.salam

Shr

func Shr(x: Int, k: int): Int
Shifts right by k bits.

The example for this item is shown with the ones above: bigint-Add.salam

Set

func Set(x &: Int, src: Int)
Replaces the value of x with a copy of src, freeing the old value.

The example for this item is shown with the ones above: bigint-AddTo.salam

SetInt

func SetInt(x &: Int, v: i64)
Replaces the value of x with an ordinary whole number, freeing the old value.

The example for this item is shown with the ones above: bigint-AddTo.salam

AddTo

func AddTo(x &: Int, y: Int)
Adds y to x: the sum replaces x and the old value is freed.

The example for this item is shown with the ones above: bigint-AddTo.salam

SubFrom

func SubFrom(x &: Int, y: Int)
Subtracts y from x.

The example for this item is shown with the ones above: bigint-AddTo.salam

MulBy

func MulBy(x &: Int, y: Int)
Multiplies x by y.

The example for this item is shown with the ones above: bigint-AddTo.salam

AddIntTo

func AddIntTo(x &: Int, v: i64)
Adds an ordinary whole number to x.

The example for this item is shown with the ones above: bigint-AddTo.salam

MulIntBy

func MulIntBy(x &: Int, v: i64)
Multiplies x by an ordinary whole number.

The example for this item is shown with the ones above: bigint-AddTo.salam

NegateIn

func NegateIn(x &: Int)
Reverses the sign of x.

The example for this item is shown with the ones above: bigint-AddTo.salam

ShlBy

func ShlBy(x &: Int, k: int)
Shifts x left in place.

The example for this item is shown with the ones above: bigint-AddTo.salam

ShrBy

func ShrBy(x &: Int, k: int)
Shifts x right in place.

The example for this item is shown with the ones above: bigint-AddTo.salam

Pow

func Pow(x: Int, e: int): Int
The number raised to the power e, by repeated squaring. A negative e gives 0.

The example for this item is shown with the ones above: bigint-Int.salam

Pow10

func Pow10(n: int): Int
Ten raised to the power n.

The example for this item is shown with the ones above: bigint-Add.salam

ModExp

func ModExp(base: Int, e: Int, m: Int): Int
Computes base to the power e modulo m without building the huge intermediate number; the basis of RSA. The result is from 0 to |m|-1. A zero m or a negative e gives 0.
bigint-ModExp.salam
import bigint

func main:
    println bigint.ToStr(bigint.Factorial(30))
    println bigint.ToStr(bigint.ModExp(bigint.FromInt(4), bigint.FromInt(13), bigint.FromInt(497)))
    println bigint.ToStr(bigint.Gcd(bigint.FromInt(48), bigint.FromInt(18))), bigint.ToStr(bigint.Lcm(bigint.FromInt(4), bigint.FromInt(6)))
    mut x := bigint.Zero()
    mut y := bigint.Zero()
    g := bigint.ExtGcd(bigint.FromInt(240), bigint.FromInt(46), x, y)
    println bigint.ToStr(g), bigint.ToStr(x), bigint.ToStr(y)
    mut ok := false
    inv := bigint.ModInverse(bigint.FromInt(3), bigint.FromInt(11), ok)
    println ok, bigint.ToStr(inv)
    println bigint.ToStr(bigint.Sqrt(bigint.Pow10(20)))
end
Output265252859812191058636308480000000 445 6 12 2 -9 47 true 4 10000000000

Gcd

func Gcd(a: Int, b: Int): Int
The greatest common divisor.

The example for this item is shown with the ones above: bigint-ModExp.salam

Lcm

func Lcm(a: Int, b: Int): Int
The least common multiple.

The example for this item is shown with the ones above: bigint-ModExp.salam

ExtGcd

func ExtGcd(a: Int, b: Int, x &: Int, y &: Int): Int
The extended greatest common divisor: besides the gcd it finds the coefficients x and y with a·x + b·y equal to the gcd.

The example for this item is shown with the ones above: bigint-ModExp.salam

ModInverse

func ModInverse(a: Int, m: Int, ok &: bool): Int
The modular inverse: the number whose product with a modulo m is one. When there is none, because a and m share a factor, ok turns false.

The example for this item is shown with the ones above: bigint-ModExp.salam

Sqrt

func Sqrt(x: Int): Int
The integer square root: the largest number whose square is not greater than this one. A negative number gives 0.

The example for this item is shown with the ones above: bigint-ModExp.salam

Factorial

func Factorial(n: int): Int
The factorial of n, with no size limit. A negative n gives 0.

The example for this item is shown with the ones above: bigint-ModExp.salam

DivMod

func DivMod(a: Int, b: Int, q &: Int, r &: Int): bool
Puts the quotient and the remainder into q and r together; the quotient is rounded towards zero. It returns false when the divisor is zero.
bigint-Div.salam
import bigint

func main:
    a := bigint.FromInt(-17)
    b := bigint.FromInt(5)
    println bigint.ToStr(bigint.Div(a, b)), bigint.ToStr(bigint.Rem(a, b))
    println bigint.ToStr(bigint.FloorDiv(a, b)), bigint.ToStr(bigint.FloorMod(a, b)), bigint.ToStr(bigint.Mod(a, b))
    mut q := bigint.Zero()
    mut r := bigint.Zero()
    println bigint.DivMod(a, b, q, r), bigint.ToStr(q), bigint.ToStr(r)
    println bigint.FloorDivMod(a, b, q, r), bigint.ToStr(q), bigint.ToStr(r)
    println bigint.DivMod(a, bigint.Zero(), q, r)
    mut rem := 0 as i64
    println bigint.ToStr(bigint.DivModInt(bigint.FromInt(100), 7, rem)), rem, bigint.ModInt(bigint.FromInt(100), 7)
end
Output-3 -2 -4 3 3 true -3 -2 true -4 3 false 14 2 2

Div

func Div(a: Int, b: Int): Int
The quotient, rounded towards zero, as in C. A zero divisor gives 0; use DivMod to detect it.

The example for this item is shown with the ones above: bigint-Div.salam

Rem

func Rem(a: Int, b: Int): Int
The remainder, with the sign of the dividend. A zero divisor gives 0.

The example for this item is shown with the ones above: bigint-Div.salam

FloorDivMod

func FloorDivMod(a: Int, b: Int, q &: Int, r &: Int): bool
Like DivMod, but the quotient is rounded down and the remainder takes the sign of the divisor, as in Python.

The example for this item is shown with the ones above: bigint-Div.salam

FloorDiv

func FloorDiv(a: Int, b: Int): Int
The quotient, rounded down.

The example for this item is shown with the ones above: bigint-Div.salam

FloorMod

func FloorMod(a: Int, b: Int): Int
The remainder of a floor division.

The example for this item is shown with the ones above: bigint-Div.salam

Mod

func Mod(a: Int, m: Int): Int
The remainder from 0 up to |m|, for modular arithmetic: Mod(-10, 3) is 2. A zero m gives 0.

The example for this item is shown with the ones above: bigint-Div.salam

DivModInt

func DivModInt(a: Int, v: i64, rem &: i64): Int
Division by an ordinary whole number; the remainder, with the sign of the dividend, goes into rem. A zero divisor gives 0 and a remainder of 0.

The example for this item is shown with the ones above: bigint-Div.salam

ModInt

func ModInt(a: Int, v: i64): i64
The remainder from 0 up to |v| of dividing by an ordinary whole number, like Mod.

The example for this item is shown with the ones above: bigint-Div.salam

And

func And(a: Int, b: Int): Int
The bitwise and of two numbers.
bigint-And.salam
import bigint

func main:
    a := bigint.FromInt(12)
    b := bigint.FromInt(10)
    println bigint.ToStr(bigint.And(a, b)), bigint.ToStr(bigint.Or(a, b)), bigint.ToStr(bigint.Xor(a, b))
    println bigint.ToStr(bigint.AndNot(a, b)), bigint.ToStr(bigint.Not(a))
    println bigint.PopCount(a), bigint.TrailingZeros(a)
end
Output8 14 6 4 -13 2 2

Or

func Or(a: Int, b: Int): Int
The bitwise or of two numbers.

The example for this item is shown with the ones above: bigint-And.salam

Xor

func Xor(a: Int, b: Int): Int
The bitwise exclusive or of two numbers.

The example for this item is shown with the ones above: bigint-And.salam

AndNot

func AndNot(a: Int, b: Int): Int
The bits of the first number that are zero in the second.

The example for this item is shown with the ones above: bigint-And.salam

Not

func Not(x: Int): Int
The bitwise complement; it behaves as two's complement for negative numbers, so the complement of 12 is −13.

The example for this item is shown with the ones above: bigint-And.salam

PopCount

func PopCount(x: Int): int
How many one bits the absolute value has.

The example for this item is shown with the ones above: bigint-And.salam

TrailingZeros

func TrailingZeros(x: Int): int
How many zero bits there are in a row from the least significant end.

The example for this item is shown with the ones above: bigint-And.salam