Skip to Content
ReferenceLibrary

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 Sieve

The smallest prime factor of every number up to n (0 for 0 and 1), by a linear sieve. O(n) time and memory.

Source

Sieve.new

fn new(n: Int) -> Sieve

A 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 < 0 or n > 2_000_000_000

Examples:

  • Sieve(10).is_prime(7) == true
  • Sieve(0).is_prime(0) == false

Source

Sieve.is_prime

fn is_prime(self, x: Int) -> Bool

Whether x is prime, for 0 <= x <= n: spf[x] == x and x >= 2.

  • cost: O(1)
  • traps: when x is outside 0..=n

Examples:

  • Sieve(10).is_prime(7) == true
  • Sieve(10).is_prime(9) == false
  • Sieve(10).is_prime(1) == false

Source

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 x is outside 1..=n

Examples:

  • Sieve(100).factor(60) == [(2, 2), (3, 1), (5, 1)]
  • Sieve(100).factor(97) == [(97, 1)]
  • Sieve(100).factor(1) == []

Source

Sieve.phi

fn phi(self, x: Int) -> Int

Euler's totient of x in 1..=n: how many of 1..=x are coprime to x.

  • cost: O(log x)
  • traps: when x is outside 1..=n

Examples:

  • Sieve(100).phi(36) == 12
  • Sieve(100).phi(1) == 1

Source

Sieve.mobius

fn mobius(self, x: Int) -> Int

The 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 x is outside 1..=n

Examples:

  • Sieve(100).mobius(30) == -1
  • Sieve(100).mobius(12) == 0
  • Sieve(100).mobius(6) == 1
  • Sieve(100).mobius(1) == 1

Source

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 key k, k in 0..=n; a new List
  • traps: never

Examples:

  • Sieve(6).phi_table() == [0, 1, 1, 2, 2, 4, 2]

Source

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 key k, k in 0..=n; a new List
  • traps: never

Examples:

  • Sieve(6).mobius_table() == [0, 1, -1, -1, 0, -1, 1]

Source

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 key k, k in 0..=n; a new List
  • traps: never

Examples:

  • Sieve(6).div_count_table() == [0, 1, 2, 2, 3, 2, 4]

Source

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 key k, k in 0..=n; a new List
  • traps: when a sum overflows Int

Examples:

  • Sieve(6).div_sum_table() == [0, 1, 3, 4, 7, 6, 12]

Source

Sieve.divisors

fn divisors(self, x: Int) -> yields Int

The 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 x is outside 1..=n

Examples:

  • Sieve(12).divisors(12).collect() == [1, 2, 4, 3, 6, 12]
  • Sieve(12).divisors(1).collect() == [1]

Source

Sign

pub enum Sign

Which 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.

Source

Sign.Neg

Neg

Source

Sign.Zero

Zero

Source

Sign.Pos

Pos

Source

DirichletSum

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.

Source

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_small makes 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

Source

DirichletSum.sum

fn sum(mut self, m: Int) -> T

The 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 / i queries
  • traps: when m is outside 0..=n, or g(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) == 32
  • var ds = DirichletSum<Int>(10, [0, 1, 1, 2, 2], m => m, m => m * (m + 1) / 2); ds.sum(0) == 0

Source

Ratio

pub struct Ratio(p: Int, q: Int)

O(1) storage. Exact reduced rational p / q (q > 0, gcd(|p|, q) == 1).

Source

Ratio.new

fn new(p: Int, q: Int = 1) -> Ratio

The 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 == -1
  • Ratio(5) == Ratio.from_int(5)

Source

Ratio.from_int

fn from_int(n: Int) -> Ratio

n as the fraction n / 1.

  • cost: O(1)
  • traps: never

Examples:

  • Ratio.from_int(3) == Ratio(3, 1)

Source

Ratio.inv

fn inv(self) -> Ratio

The 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)

Source

Ratio.floor

fn floor(self) -> Int

The floor of p / q (Euclidean division).

  • cost: O(1)
  • traps: never

Examples:

  • Ratio(7, 2).floor == 3
  • Ratio(-7, 2).floor == -4

Source

Ratio.ceil

fn ceil(self) -> Int

The ceiling of p / q: ceil_div(p, q).

  • cost: O(1)
  • traps: never

Examples:

  • Ratio(7, 2).ceil == 4
  • Ratio(-7, 2).ceil == -3

Source

Ratio.abs

fn abs(self) -> Ratio

The absolute value |p| / q.

  • cost: O(1)
  • traps: never

Examples:

  • Ratio(-1, 2).abs == Ratio(1, 2)

Source

Ratio

impl Add for Ratio

Source

Ratio.add

fn add(a, b)

Source

Ratio

impl Sub for Ratio

Source

Ratio.sub

fn sub(a, b)

Source

Ratio

impl Neg for Ratio

Source

Ratio.neg

fn neg(a)

Source

Ratio

impl Mul for Ratio

Source

Ratio.mul

fn mul(a, b)

Source

Ratio

impl Div for Ratio

Source

Ratio.div

fn div(a, b)

Source

Ratio

impl Ord for Ratio

Source

Ratio.lt

fn lt(a, b)

Source

Ratio

impl Show for Ratio

Source

Ratio.show

fn show(a)

Source

BigInt

pub struct BigInt(neg: Bool, limbs: List<Int>)

O(n) storage in base-10^9 limbs. Arbitrary-precision signed integer.

Source

BigInt.from_int

fn from_int(x: Int) -> BigInt

x as a BigInt.

  • cost: O(1)
  • traps: never

Examples:

  • BigInt.from_int(-42).to_str() == "-42"

Source

BigInt.from_str

fn from_str(s: Str) -> BigInt

Parse 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 s is 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"

Source

BigInt.to_str

fn to_str(self) -> Str

The 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"

Source

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 d is 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))

Source

BigInt.abs

fn abs(self) -> BigInt

The absolute value.

  • cost: O(n)
  • traps: never

Examples:

  • BigInt.from_int(-5).abs() == BigInt.from_int(5)

Source

BigInt.gcd

fn gcd(a: BigInt, b: BigInt) -> BigInt

The 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)

Source

BigInt

impl Add for BigInt

Source

BigInt.add

fn add(a, b)

Source

BigInt

impl Sub for BigInt

Source

BigInt.sub

fn sub(a, b)

Source

BigInt

impl Neg for BigInt

Source

BigInt.neg

fn neg(a)

Source

BigInt

impl Mul for BigInt

Source

BigInt.mul

fn mul(a, b)

Source

BigInt

impl Div for BigInt

Source

BigInt.div

fn div(a, b)

Source

BigInt

impl Ord for BigInt

Source

BigInt.lt

fn lt(a, b)

Source

BigInt

impl Show for BigInt

Source

BigInt.show

fn show(a)

Source

inf

pub const inf: Int = 9_223_372_036_854_775_807

Int.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).

Source

On this page