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.
Mod.MOD
let MODThe modulus: Z.MOD.
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)
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() == NoneMod<7>(0).try_inv() == None
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)
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)
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
Pis not prime
Examples:
Mod<7>(2).sqrt() == Some(Mod<7>(3))Mod<7>(3).sqrt() == NoneMod<7>(0).sqrt() == Some(Mod<7>(0))
Mod.log
fn log(self, target: Mod<P>) -> ?IntThe 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
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 newList, 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) == []
Mod<P>
impl Add for Mod<P>Mod<P>.add
fn add(a, b)Mod<P>
impl Sub for Mod<P>Mod<P>.sub
fn sub(a, b)Mod<P>
impl Neg for Mod<P>Mod<P>.neg
fn neg(a)Mod<P>
impl Mul for Mod<P>Mod<P>.mul
fn mul(a, b)Mod<P>
impl Div for Mod<P>Mod<P>.div
fn div(a, b)Mod<P>
impl Pow for Mod<P>Mod<P>.pow
fn pow(a, e: Int) -> Mod<P>Mod<P>
impl Show for Mod<P>Mod<P>.show
fn show(a)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)
Mod<P>.read
fn read() -> Mod<P>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.
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, orPis not prime
Examples:
type Z = Mod<7>; let c = Comb<Z>(3); c.fact(3) == Z(6)
Comb.grow
fn grow(self, want: Int)Comb.ensure
fn ensure(self, n: Int)Comb.fact
fn fact(self, n: Int) -> Mn!, 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)
Comb.inv_fact
fn inv_fact(self, n: Int) -> M1 / n!, for 0 <= n < M.MOD.
- cost: O(1) amortized
- traps: when
nis outside0..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)
Comb.inv
fn inv(self, i: Int) -> M1 / i, for 1 <= i < M.MOD, from the factorials: (i - 1)! / i!.
- cost: O(1) amortized
- traps: when
iis outside1..M.MOD
Examples:
type Z = Mod<7>; Comb<Z>().inv(3) == Z(5)
Comb.choose_lucas
fn choose_lucas(self, n: Int, k: Int) -> MComb.choose
fn choose(self, n: Int, k: Int) -> MThe 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)
Comb.arrange
fn arrange(self, n: Int, k: Int) -> MThe 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)
Comb.multichoose
fn multichoose(self, n: Int, k: Int) -> MThe 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)
Comb.catalan
fn catalan(self, n: Int) -> MThe 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)
Comb.derange
fn derange(self, n: Int) -> MThe 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)
Comb.multinomial
fn multinomial(self, ks: List<Int>) -> MThe 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)
Barrett
pub struct Barrett(m: Int, im: U64)O(1) reduction. Fast Barrett modular multiplier for a runtime modulus 1 <= m < 2^31.
Barrett.new
fn new(m: Int) -> BarrettA 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
mis outside1..2^31
Examples:
Barrett(7).mul(3, 5) == 1
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
aorbis outside0..m
Examples:
Barrett(7).mul(3, 5) == 1Barrett(1_000_000_007).mul(1_000_000_006, 1_000_000_006) == 1Barrett(1).mul(0, 0) == 0
Barrett.reduce
fn reduce(self, a: U64) -> Inta % m, for a < m * m.
- cost: O(1)
- traps: when
a >= m * m
Examples:
Barrett(7).reduce(48) == 6Barrett(7).reduce(0) == 0
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).
PrimePowerComb.new
fn new(p: Int, e: Int) -> PrimePowerCombTables 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
pis not prime, ore < 1, orp^eoverflowsInt
Examples:
PrimePowerComb(2, 3).choose(6, 3) == 4
PrimePowerComb.free_fact
fn free_fact(self, n: Int) -> IntPrimePowerComb.p_count
fn p_count(self, n: Int) -> IntPrimePowerComb.choose
fn choose(self, n: Int, k: Int) -> IntC(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) == 4PrimePowerComb(3, 2).choose(9, 3) == 3PrimePowerComb(3, 2).choose(5, 7) == 0
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.
ModComb.new
fn new(m: Int) -> ModCombBinomial 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
ModComb.choose
fn choose(self, n: Int, k: Int) -> IntC(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) == 8ModComb(10).choose(5, 2) == 0ModComb(1).choose(5, 2) == 0