math
The greatest common divisor of a and b, never negative; gcd(0, 0) == 0.
Generated from spec/std/math.cp by cpl doc --format json.
Sieve
pub struct SieveThe smallest prime factor of every number up to n (0 for 0 and 1), by a linear sieve.
O(n) time and memory.
Sieve.new
fn new(n: Int) -> SieveA linear sieve up to n: the smallest prime factor of every 0..=n and the primes in
2..=n, ascending.
spf[0] and spf[1] are 0. Queries take any x in 0..=n (1..=n where 0 is meaningless).
- cost: O(n) time and memory
- traps: when
n < 0orn > 2_000_000_000
Examples:
Sieve(10).is_prime(7) == trueSieve(0).is_prime(0) == false
Sieve.is_prime
fn is_prime(self, x: Int) -> BoolWhether x is prime, for 0 <= x <= n: spf[x] == x and x >= 2.
- cost: O(1)
- traps: when
xis outside0..=n
Examples:
Sieve(10).is_prime(7) == trueSieve(10).is_prime(9) == falseSieve(10).is_prime(1) == false
Sieve.factor
fn factor(self, x: Int) -> List<(Int, Int)>The prime factorization of x in 1..=n as (prime, exponent) pairs, by repeated spf.
- cost: O(log x)
- order: smallest prime first; a new
List, keyed from 0 - traps: when
xis outside1..=n
Examples:
Sieve(100).factor(60) == [(2, 2), (3, 1), (5, 1)]Sieve(100).factor(97) == [(97, 1)]Sieve(100).factor(1) == []
Sieve.phi
fn phi(self, x: Int) -> IntEuler's totient of x in 1..=n: how many of 1..=x are coprime to x.
- cost: O(log x)
- traps: when
xis outside1..=n
Examples:
Sieve(100).phi(36) == 12Sieve(100).phi(1) == 1
Sieve.mobius
fn mobius(self, x: Int) -> IntThe Mobius function of x in 1..=n: 0 if a square above 1 divides x, else -1 to the
number of prime factors.
- cost: O(log x)
- traps: when
xis outside1..=n
Examples:
Sieve(100).mobius(30) == -1Sieve(100).mobius(12) == 0Sieve(100).mobius(6) == 1Sieve(100).mobius(1) == 1
Sieve.phi_table
fn phi_table(self) -> List<Int>Euler's totient of every 0..=n, with phi[0] == 0.
- cost: O(n)
- order:
phi[k]at keyk,kin0..=n; a newList - traps: never
Examples:
Sieve(6).phi_table() == [0, 1, 1, 2, 2, 4, 2]
Sieve.mobius_table
fn mobius_table(self) -> List<Int>The Mobius function of every 0..=n, with mu[0] == 0 and mu[1] == 1.
- cost: O(n)
- order:
mu[k]at keyk,kin0..=n; a newList - traps: never
Examples:
Sieve(6).mobius_table() == [0, 1, -1, -1, 0, -1, 1]
Sieve.div_count_table
fn div_count_table(self) -> List<Int>The number of positive divisors of every 0..=n, with d[0] == 0.
- cost: O(n)
- order:
d[k]at keyk,kin0..=n; a newList - traps: never
Examples:
Sieve(6).div_count_table() == [0, 1, 2, 2, 3, 2, 4]
Sieve.div_sum_table
fn div_sum_table(self) -> List<Int>The sum of the positive divisors of every 0..=n, with sigma[0] == 0.
- cost: O(n)
- order:
sigma[k]at keyk,kin0..=n; a newList - traps: when a sum overflows
Int
Examples:
Sieve(6).div_sum_table() == [0, 1, 3, 4, 7, 6, 12]
Sieve.divisors
fn divisors(self, x: Int) -> yields IntThe positive divisors of x in 1..=n, built from the factorization, with no allocation.
They come in mixed-radix order over the factorization: the exponent of the smallest prime
changes fastest. That order is fixed but not sorted; use .sorted() for ascending.
- cost: O(log x) to start, O(1) per divisor
- order: mixed-radix over the exponents, smallest prime fastest (12 gives 1, 2, 4, 3, 6, 12)
- traps: when
xis outside1..=n
Examples:
Sieve(12).divisors(12).collect() == [1, 2, 4, 3, 6, 12]Sieve(12).divisors(1).collect() == [1]
Sign
pub enum SignWhich side of zero a number is on. Int(s) is -1, 0 or 1, so x == Int(x.sign) * abs(x);
-s flips it and max(s, Sign.Zero) clamps it.
Sign.Neg
NegSign.Zero
ZeroSign.Pos
PosDirichletSum
pub struct DirichletSum<T>O(n^(2/3)) time and memory. Stateful Du's sieve cache for prefix sums of a multiplicative function f
given prefix sums of g and f * g.
DirichletSum.new
fn new(n: Int, f_small: List<T>, g_sum: Int -> T, fg_sum: Int -> T) -> DirichletSum<T>A Du's-sieve cache for the prefix sums F(m) = sum_{k=1..=m} f(k) of a multiplicative f, up
to n.
f_small[k] is f(k) for k in 1..f_small.len (index 0 ignored); sums up to there come
from its prefix sums. Larger m use g_sum(m) = sum_{k<=m} g(k) and fg_sum(m) = sum_{k<=m} (f * g)(k) for a Dirichlet partner g with g(1) invertible:
F(m) = (fg_sum(m) - sum_{i=2..=m} g(i) F(m / i)) / g(1), grouped by floor quotients and
memoized. A table of about n^(2/3) entries gives the stated cost.
- cost: O(f_small.len) to build; queries as
sum - empty: an empty
f_smallmakes every query use the recursion - traps: when
n < 0
Examples:
var ds = DirichletSum<Int>(10, [0, 1, 1, 2, 2], m => m, m => m * (m + 1) / 2); ds.sum(10) == 32
DirichletSum.sum
fn sum(mut self, m: Int) -> TThe prefix sum F(m) = sum_{k=1..=m} f(k), with F(0) == 0.
Results are memoized, so all the n / i values together cost O(n^(2/3)) when f_small has
about n^(2/3) entries.
- cost: O(1) cached; O(n^(2/3)) total across all
n / iqueries - traps: when
mis outside0..=n, org(1)is not invertible
Examples:
var ds = DirichletSum<Int>(10, [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4], m => m, m => m * (m + 1) / 2); ds.sum(10) == 32var ds = DirichletSum<Int>(10, [0, 1, 1, 2, 2], m => m, m => m * (m + 1) / 2); ds.sum(0) == 0
Ratio
pub struct Ratio(p: Int, q: Int)O(1) storage. Exact reduced rational p / q (q > 0, gcd(|p|, q) == 1).
Ratio.new
fn new(p: Int, q: Int = 1) -> RatioThe fraction p / q in lowest terms, with a positive denominator.
- cost: O(log min(|p|, |q|))
- traps: when
q == 0
Examples:
Ratio(2, 4) == Ratio(1, 2)Ratio(3, -6).floor == -1Ratio(5) == Ratio.from_int(5)
Ratio.from_int
fn from_int(n: Int) -> Ration as the fraction n / 1.
- cost: O(1)
- traps: never
Examples:
Ratio.from_int(3) == Ratio(3, 1)
Ratio.inv
fn inv(self) -> RatioThe multiplicative inverse q / p, sign moved to the numerator.
- cost: O(1)
- traps: when
p == 0
Examples:
Ratio(-2, 3).inv == Ratio(-3, 2)Ratio(1, 4).inv == Ratio.from_int(4)
Ratio.floor
fn floor(self) -> IntThe floor of p / q (Euclidean division).
- cost: O(1)
- traps: never
Examples:
Ratio(7, 2).floor == 3Ratio(-7, 2).floor == -4
Ratio.ceil
fn ceil(self) -> IntThe ceiling of p / q: ceil_div(p, q).
- cost: O(1)
- traps: never
Examples:
Ratio(7, 2).ceil == 4Ratio(-7, 2).ceil == -3
Ratio.abs
fn abs(self) -> RatioThe absolute value |p| / q.
- cost: O(1)
- traps: never
Examples:
Ratio(-1, 2).abs == Ratio(1, 2)
Ratio
impl Add for RatioRatio.add
fn add(a, b)Ratio
impl Sub for RatioRatio.sub
fn sub(a, b)Ratio
impl Neg for RatioRatio.neg
fn neg(a)Ratio
impl Mul for RatioRatio.mul
fn mul(a, b)Ratio
impl Div for RatioRatio.div
fn div(a, b)Ratio
impl Ord for RatioRatio.lt
fn lt(a, b)Ratio
impl Show for RatioRatio.show
fn show(a)BigInt
pub struct BigInt(neg: Bool, limbs: List<Int>)O(n) storage in base-10^9 limbs. Arbitrary-precision signed integer.
BigInt.from_int
fn from_int(x: Int) -> BigIntx as a BigInt.
- cost: O(1)
- traps: never
Examples:
BigInt.from_int(-42).to_str() == "-42"
BigInt.from_str
fn from_str(s: Str) -> BigIntParse a decimal integer: an optional leading -, then one or more digits.
Leading zeros are allowed, and -0 is zero. There is no + and no whitespace.
- cost: O(s.len)
- traps: when
sis not an optional-followed by at least one decimal digit
Examples:
BigInt.from_str("-000123").to_str() == "-123"BigInt.from_str("-0").to_str() == "0"BigInt.from_str("123456789012345678901234567890").to_str() == "123456789012345678901234567890"
BigInt.to_str
fn to_str(self) -> StrThe decimal text of self: no leading zeros, a - only when negative, "0" for zero.
- cost: O(n)
- traps: never
Examples:
BigInt.from_int(0).to_str() == "0"BigInt.from_int(-7).to_str() == "-7"
BigInt.divmod
fn divmod(self, d: BigInt) -> (BigInt, BigInt)The Euclidean quotient and remainder (self / d, self % d): 0 <= r < |d|, as for Int.
- cost: O(n * m)
- traps: when
dis zero
Examples:
BigInt.from_int(-7).divmod(BigInt.from_int(3)) == (BigInt.from_int(-3), BigInt.from_int(2))BigInt.from_int(7).divmod(BigInt.from_int(-3)) == (BigInt.from_int(-2), BigInt.from_int(1))
BigInt.abs
fn abs(self) -> BigIntThe absolute value.
- cost: O(n)
- traps: never
Examples:
BigInt.from_int(-5).abs() == BigInt.from_int(5)
BigInt.gcd
fn gcd(a: BigInt, b: BigInt) -> BigIntThe greatest common divisor of a and b, never negative; gcd(0, 0) is 0.
- cost: O(n^2)
- traps: never
Examples:
BigInt.gcd(BigInt.from_int(12), BigInt.from_int(-18)) == BigInt.from_int(6)BigInt.gcd(BigInt.from_int(0), BigInt.from_int(0)) == BigInt.from_int(0)
BigInt
impl Add for BigIntBigInt.add
fn add(a, b)BigInt
impl Sub for BigIntBigInt.sub
fn sub(a, b)BigInt
impl Neg for BigIntBigInt.neg
fn neg(a)BigInt
impl Mul for BigIntBigInt.mul
fn mul(a, b)BigInt
impl Div for BigIntBigInt.div
fn div(a, b)BigInt
impl Ord for BigIntBigInt.lt
fn lt(a, b)BigInt
impl Show for BigIntBigInt.show
fn show(a)inf
pub const inf: Int = 9_223_372_036_854_775_807Int.MAX, for Int tables that start "unreached" when ?Int with None is not wanted.
min treats it as its identity; adding to it overflows (a trap in checked builds).