Skip to Content
ReferenceLibrary

mod

An integer modulo the constant P, always stored in 0..P.

Generated from spec/std/mod.cp by cpl doc --format json.

Mod

pub struct Mod<P>(v: 0..P)

An integer modulo the constant P, always stored in 0..P. + - * are O(1); / and inv are O(log P) and need gcd(x, P) == 1.

Source

Mod.MOD

let MOD

The modulus: Z.MOD.

Source

Mod.new

fn new(x: Int) -> Mod<P>

Any Int, reduced into 0..P by Euclidean remainder: Mod<7>(-1) is 6.

Mod<P>(x) calls new, so every way of building a Mod reduces.

  • cost: O(1)
  • traps: never

Examples:

  • Mod<7>(-1) == Mod<7>(6)
  • Mod<7>(15) == Mod<7>(1)
  • Mod<1>(5) == Mod<1>(0)

Source

Mod.try_inv

fn try_inv(self) -> ?Mod<P>

The multiplicative inverse when gcd(v, P) == 1, or None otherwise.

Uses the extended Euclidean algorithm, so P need not be prime. With P == 1 the only value is 0, which is also one, so Mod<1>(0).try_inv() is Some(Mod<1>(0)).

  • cost: O(log P)
  • traps: never

Examples:

  • Mod<7>(3).try_inv() == Some(Mod<7>(5))
  • Mod<6>(4).try_inv() == None
  • Mod<7>(0).try_inv() == None

Source

Mod.inv

fn inv(self) -> Mod<P>

The multiplicative inverse, by the extended Euclidean algorithm (so P need not be prime).

x.inv() is x.try_inv().unwrap() with a trap that names x and P; a / b is a * b.inv().

  • cost: O(log P)
  • traps: when gcd(v, P) != 1

Examples:

  • Mod<7>(3).inv() == Mod<7>(5)
  • Mod<10>(3).inv() == Mod<10>(7)

Source

Mod.from_int

fn from_int(x: Int) -> Mod<P>

Lift an Int to Mod<P>; the same reduction as new.

This is the conversion an Int literal takes where a Mod<P> is expected, so let x: Mod<7> = 10 is Mod<7>.from_int(10).

  • cost: O(1)
  • traps: never

Examples:

  • Mod<7>.from_int(10) == Mod<7>(3)
  • Mod<7>.from_int(-8) == Mod<7>(6)

Source

Mod.sqrt

fn sqrt(self) -> ?Mod<P>

A square root modulo the prime P (Tonelli-Shanks), or None when there is None.

Of the two roots r and P - r, it returns the one with the smaller value v; the root of 0 is 0.

  • cost: O(log^2 P)
  • ties: the root with the smaller value
  • traps: when P is not prime

Examples:

  • Mod<7>(2).sqrt() == Some(Mod<7>(3))
  • Mod<7>(3).sqrt() == None
  • Mod<7>(0).sqrt() == Some(Mod<7>(0))

Source

Mod.log

fn log(self, target: Mod<P>) -> ?Int

The least k >= 0 with self ** k == target (baby-step giant-step), or None.

Any modulus works: the non-coprime part is peeled off first. self ** 0 is one, so x.log(one) is Some(0) for every x.

  • cost: O(sqrt P)
  • ties: the least k
  • traps: never

Examples:

  • Mod<7>(3).log(Mod<7>(6)) == Some(3)
  • Mod<7>(3).log(Mod<7>(1)) == Some(0)
  • Mod<7>(2).log(Mod<7>(3)) == None

Source

Mod.inv_all

fn inv_all(xs: List<Mod<P>>) -> List<Mod<P>>

The inverse of every element of xs, with one inv in all (Montgomery's trick).

  • cost: O(n + log P)
  • empty: []
  • order: same order as xs; a new List, keyed from 0
  • traps: when any element has gcd(v, P) != 1 (in particular 0)

Examples:

  • Mod<7>.inv_all([Mod<7>(1), Mod<7>(2), Mod<7>(3)]) == [Mod<7>(1), Mod<7>(4), Mod<7>(5)]
  • let e: List<Mod<7>> = []; Mod<7>.inv_all(e) == []

Source

Mod<P>

impl Add for Mod<P>

Source

Mod<P>.add

fn add(a, b)

Source

Mod<P>

impl Sub for Mod<P>

Source

Mod<P>.sub

fn sub(a, b)

Source

Mod<P>

impl Neg for Mod<P>

Source

Mod<P>.neg

fn neg(a)

Source

Mod<P>

impl Mul for Mod<P>

Source

Mod<P>.mul

fn mul(a, b)

Source

Mod<P>

impl Div for Mod<P>

Source

Mod<P>.div

fn div(a, b)

Source

Mod<P>

impl Pow for Mod<P>

Source

Mod<P>.pow

fn pow(a, e: Int) -> Mod<P>

Source

Mod<P>

impl Show for Mod<P>

Source

Mod<P>.show

fn show(a)

Source

Mod<P>

impl Read for Mod<P>

One signed integer token of any length, reduced modulo P, so a 10^4-digit coefficient is read<Mod<P>>(). (R10.2.3)

Source

Mod<P>.read

fn read() -> Mod<P>

Source

Comb

pub struct Comb<M>

Factorials and inverse factorials for a modular type M = Mod<P> (prime P). Its tables are @cache fields that grow on demand, so an immutable let c = Comb<Z>() (or Comb<Z>(limit) to pre-size) answers queries in O(1) with amortized O(1) growth per new factorial.

Source

Comb.new

fn new(limit: Int = 0) -> Comb<M>

Precompute factorials and inverse factorials up to limit for M = Mod<P>, P prime.

The tables hold min(limit, P - 1) + 1 entries and grow on demand later (doubling, capped at P), so Comb<Z>() with no limit is valid and simply grows on first use.

  • cost: O(min(limit, P))
  • traps: when limit < 0, or P is not prime

Examples:

  • type Z = Mod<7>; let c = Comb<Z>(3); c.fact(3) == Z(6)

Source

Comb.grow

fn grow(self, want: Int)

Source

Comb.ensure

fn ensure(self, n: Int)

Source

Comb.fact

fn fact(self, n: Int) -> M

n!, reduced; 0 when n >= M.MOD (the product contains P).

  • cost: O(1) amortized
  • traps: when n < 0

Examples:

  • type Z = Mod<1_000_000_007>; Comb<Z>().fact(5) == Z(120)
  • type Z = Mod<7>; Comb<Z>().fact(6) == Z(6)
  • type Z = Mod<7>; Comb<Z>().fact(7) == Z(0)

Source

Comb.inv_fact

fn inv_fact(self, n: Int) -> M

1 / n!, for 0 <= n < M.MOD.

  • cost: O(1) amortized
  • traps: when n is outside 0..M.MOD

Examples:

  • type Z = Mod<7>; Comb<Z>().inv_fact(3) == Z(6)
  • type Z = Mod<7>; Comb<Z>().inv_fact(0) == Z(1)

Source

Comb.inv

fn inv(self, i: Int) -> M

1 / i, for 1 <= i < M.MOD, from the factorials: (i - 1)! / i!.

  • cost: O(1) amortized
  • traps: when i is outside 1..M.MOD

Examples:

  • type Z = Mod<7>; Comb<Z>().inv(3) == Z(5)

Source

Comb.choose_lucas

fn choose_lucas(self, n: Int, k: Int) -> M

Source

Comb.choose

fn choose(self, n: Int, k: Int) -> M

The number of k-subsets of n things, n! / (k! (n - k)!); 0 when k is outside 0..=n.

For n < M.MOD it reads the tables. For n >= M.MOD it uses Lucas's theorem on the base-P digits, so the answer is exact modulo P for every n. A negative n gives 0.

  • cost: O(1) amortized for n < M.MOD; O(log_P n) otherwise
  • traps: never

Examples:

  • type Z = Mod<1_000_000_007>; Comb<Z>().choose(5, 2) == Z(10)
  • type Z = Mod<1_000_000_007>; Comb<Z>().choose(5, 6) == Z(0)
  • type Z = Mod<7>; Comb<Z>().choose(10, 3) == Z(1)
  • type Z = Mod<7>; Comb<Z>().choose(7, 1) == Z(0)

Source

Comb.arrange

fn arrange(self, n: Int, k: Int) -> M

The number of ordered selections of k out of n things, n! / (n - k)!; 0 when k is outside 0..=n.

The value is the falling factorial n (n - 1) ... (n - k + 1) reduced modulo P: 0 when those k numbers include a multiple of P, else fact(n % P) / fact((n - k) % P), so it is exact for n >= M.MOD too.

  • cost: O(1) amortized
  • traps: never

Examples:

  • type Z = Mod<1_000_000_007>; Comb<Z>().arrange(5, 2) == Z(20)
  • type Z = Mod<7>; Comb<Z>().arrange(9, 2) == Z(2)
  • type Z = Mod<7>; Comb<Z>().arrange(8, 2) == Z(0)

Source

Comb.multichoose

fn multichoose(self, n: Int, k: Int) -> M

The number of ways to put n equal balls into k boxes (stars and bars): choose(n + k - 1, n).

multichoose(0, 0) is 1 (the empty placement) and multichoose(n, 0) is 0 for n > 0; a negative n or k gives 0.

  • cost: O(1) amortized
  • traps: never

Examples:

  • type Z = Mod<1_000_000_007>; Comb<Z>().multichoose(3, 2) == Z(4)
  • type Z = Mod<1_000_000_007>; Comb<Z>().multichoose(2, 3) == Z(6)
  • type Z = Mod<1_000_000_007>; Comb<Z>().multichoose(0, 0) == Z(1)

Source

Comb.catalan

fn catalan(self, n: Int) -> M

The n-th Catalan number, choose(2n, n) - choose(2n, n + 1).

The difference form needs no division by n + 1, so it stays exact when n + 1 is a multiple of P.

  • cost: O(1) amortized
  • traps: when n < 0

Examples:

  • type Z = Mod<1_000_000_007>; Comb<Z>().catalan(0) == Z(1)
  • type Z = Mod<1_000_000_007>; Comb<Z>().catalan(4) == Z(14)
  • type Z = Mod<7>; Comb<Z>().catalan(4) == Z(0)

Source

Comb.derange

fn derange(self, n: Int) -> M

The number of derangements !n: permutations of n things with no fixed point.

!0 = 1, !1 = 0, and !n = (n - 1)(!(n - 1) + !(n - 2)); the values are tabled like the factorials.

  • cost: O(1) amortized, O(n) table
  • traps: when n < 0

Examples:

  • type Z = Mod<1_000_000_007>; Comb<Z>().derange(0) == Z(1)
  • type Z = Mod<1_000_000_007>; Comb<Z>().derange(4) == Z(9)
  • type Z = Mod<1_000_000_007>; Comb<Z>().derange(5) == Z(44)

Source

Comb.multinomial

fn multinomial(self, ks: List<Int>) -> M

The multinomial coefficient (sum ks)! / prod(k!); 0 if any k < 0.

It is computed as the product of choose(k_1 + ... + k_i, k_i), so Lucas applies and the result is exact modulo P even when sum ks >= M.MOD.

  • cost: O(ks.len) amortized
  • empty: 1 (the empty multinomial)
  • traps: never

Examples:

  • type Z = Mod<1_000_000_007>; Comb<Z>().multinomial([2, 1]) == Z(3)
  • type Z = Mod<1_000_000_007>; Comb<Z>().multinomial([1, 1, 1]) == Z(6)
  • type Z = Mod<1_000_000_007>; Comb<Z>().multinomial([2, -1]) == Z(0)
  • type Z = Mod<1_000_000_007>; Comb<Z>().multinomial([]) == Z(1)

Source

Barrett

pub struct Barrett(m: Int, im: U64)

O(1) reduction. Fast Barrett modular multiplier for a runtime modulus 1 <= m < 2^31.

Source

Barrett.new

fn new(m: Int) -> Barrett

A Barrett multiplier for the runtime modulus m, 1 <= m < 2^31: precomputes im = floor((2^64 - 1) / m) + 1 (wrapping, so 0 for m == 1).

  • cost: O(1)
  • traps: when m is outside 1..2^31

Examples:

  • Barrett(7).mul(3, 5) == 1

Source

Barrett.mul

fn mul(self, a: Int, b: Int) -> Int

(a * b) % m without a hardware division, for a, b in 0..m.

  • cost: O(1)
  • traps: when a or b is outside 0..m

Examples:

  • Barrett(7).mul(3, 5) == 1
  • Barrett(1_000_000_007).mul(1_000_000_006, 1_000_000_006) == 1
  • Barrett(1).mul(0, 0) == 0

Source

Barrett.reduce

fn reduce(self, a: U64) -> Int

a % m, for a < m * m.

  • cost: O(1)
  • traps: when a >= m * m

Examples:

  • Barrett(7).reduce(48) == 6
  • Barrett(7).reduce(0) == 0

Source

PrimePowerComb

pub struct PrimePowerComb(p: Int, e: Int, pe: Int)

O(p^e) build, O(log_p n) query. Binomial coefficients modulo a prime power p^e (Granville's theorem).

Source

PrimePowerComb.new

fn new(p: Int, e: Int) -> PrimePowerComb

Tables for binomial coefficients modulo p^e: the factorials with every factor of p removed, modulo p^e.

  • cost: O(p^e) time and memory
  • traps: when p is not prime, or e < 1, or p^e overflows Int

Examples:

  • PrimePowerComb(2, 3).choose(6, 3) == 4

Source

PrimePowerComb.free_fact

fn free_fact(self, n: Int) -> Int

Source

PrimePowerComb.p_count

fn p_count(self, n: Int) -> Int

Source

PrimePowerComb.choose

fn choose(self, n: Int, k: Int) -> Int

C(n, k) mod p^e, by Granville's generalization of Lucas's theorem; 0 when k is outside 0..=n.

  • cost: O(log_p n)
  • traps: never

Examples:

  • PrimePowerComb(2, 3).choose(6, 3) == 4
  • PrimePowerComb(3, 2).choose(9, 3) == 3
  • PrimePowerComb(3, 2).choose(5, 7) == 0

Source

ModComb

pub struct ModComb(m: Int)

O(sum p_i^e_i) build, O(omega(m) log n) query. Binomial coefficients modulo any m >= 1 via CRT.

Source

ModComb.new

fn new(m: Int) -> ModComb

Binomial coefficients modulo any m >= 1: factor m and build one PrimePowerComb per prime power, combined by CRT.

  • cost: O(sum p_i^e_i)
  • traps: when m < 1

Examples:

  • ModComb(12).choose(6, 3) == 8

Source

ModComb.choose

fn choose(self, n: Int, k: Int) -> Int

C(n, k) mod m, by CRT over the prime powers of m; 0 when k is outside 0..=n.

With m == 1 every answer is 0.

  • cost: O(omega(m) log n)
  • traps: never

Examples:

  • ModComb(12).choose(6, 3) == 8
  • ModComb(10).choose(5, 2) == 0
  • ModComb(1).choose(5, 2) == 0

Source

On this page