Skip to Content
ReferenceLibrary

poly

The poly module.

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

Poly

pub struct Poly<T>(c: List<T>)

O(n) storage. Algebraic polynomial / formal power series wrapper over T (lowest degree first).

Source

Poly.new

fn new(c: List<T>) -> Poly<T>

A polynomial with coefficients c, lowest degree first, stored as given (trailing zeros kept, so len is c.len).

  • cost: O(n)
  • empty: Poly.new([]) is the zero polynomial
  • traps: never

Examples:

  • Poly<Int>([1, 2, 0]).len == 3

Source

Poly.from_int

fn from_int(v: Int) -> Poly<T>

The constant polynomial v, with one coefficient T.from_int(v).

  • cost: O(1)
  • traps: never

Examples:

  • Poly<Int>.from_int(5).at(0) == 5

Source

Poly.zero

fn zero() -> Poly<T>

The zero polynomial 0, with no coefficients.

  • cost: O(1)
  • traps: never

Examples:

  • Poly<Int>.zero.deg() == -1 and Poly<Int>.zero.len == 0

Source

Poly.one

fn one() -> Poly<T>

The constant polynomial 1.

  • cost: O(1)
  • traps: never

Examples:

  • Poly<Int>.one.at(0) == 1 and Poly<Int>.one.deg() == 0

Source

Poly.x

fn x() -> Poly<T>

The indeterminate x: coefficients [0, 1].

  • cost: O(1)
  • traps: never

Examples:

  • Poly<Int>.x.deg() == 1 and Poly<Int>.x.at(1) == 1

Source

Poly.len

fn len(self) -> Int

The number of stored coefficients, trailing zeros included.

  • cost: O(1)
  • traps: never

Examples:

  • Poly<Int>([1, 0]).len == 2

Source

Poly.deg

fn deg(self) -> Int

The degree: the highest index with a nonzero coefficient, -1 for the zero polynomial. Stored trailing zeros do not count.

  • cost: O(1) plus the number of stored trailing zeros
  • traps: never

Examples:

  • Poly<Int>([1, 2, 0]).deg() == 1
  • Poly<Int>([0, 0]).deg() == -1

Source

Poly.is_zero

fn is_zero(self) -> Bool

Whether all coefficients are zero (including when there are None).

  • cost: O(1) plus the number of stored trailing zeros
  • traps: never

Examples:

  • Poly<Int>([0, 0]).is_zero() and not Poly<Int>.one.is_zero()

Source

Poly.at

fn at(self, i: Int) -> T

Read coefficient i (0 when i >= self.len).

  • cost: O(1)
  • traps: when i < 0

Examples:

  • Poly<Int>([1, 2]).at(1) == 2 and Poly<Int>([1, 2]).at(5) == 0

Source

Poly.set

fn set(mut self, i: Int, v: T)

Write coefficient i, growing with zeros if needed.

  • cost: O(1), or O(i) when it grows
  • traps: when i < 0

Examples:

  • var p = Poly<Int>([1]); p.set(3, 7); p.len == 4 and p.at(2) == 0 and p.at(3) == 7

Source

Poly.deriv

fn deriv(self) -> Poly<T>

The formal derivative f'(x), as the free deriv does on the coefficients.

  • cost: O(n)
  • traps: never

Examples:

  • Poly<Int>([1, 2, 3]).deriv().at(1) == 6

Source

Poly.integral

fn integral(self) -> Poly<T>

The formal integral with zero constant term, as the free integral.

  • cost: O(n)
  • traps: when T cannot divide by some k in 1..=n (n >= P for Mod<P>)

Examples:

  • type Z = Mod<998244353>; Poly<Z>([1, 2, 3]).integral().at(3) == Z(1)

Source

Poly.transposed_mul

fn transposed_mul(self, b: Poly<T>) -> Poly<T>

The transposed (middle) product: out[i] = sum_j self[i + j] * b[j] over j in 0..b.len, for each i in 0..max(0, self.len - b.len + 1) (only complete sums).

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

Examples:

  • Poly<Int>([1, 2, 3, 4]).transposed_mul(Poly<Int>([1, 1])).len == 3
  • Poly<Int>([1, 2, 3, 4]).transposed_mul(Poly<Int>([1, 1])).at(2) == 7

Source

Poly.truncated

fn truncated(self, n: Int) -> Poly<T>

Truncate or zero-pad to exactly n coefficients (mod x^n).

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

Examples:

  • Poly<Int>([1, 2, 3]).truncated(2).len == 2
  • Poly<Int>([1]).truncated(3).at(2) == 0

Source

Poly.inv

fn inv(self, n: Int) -> Poly<T>

The multiplicative inverse mod x^n (self[0] != 0), as the free inv.

  • cost: O(n log n)
  • traps: as the free inv: n < 0, or n > 0 with self.at(0) == 0

Examples:

  • type Z = Mod<998244353>; Poly<Z>([1, -1]).inv(3).at(2) == Z(1)

Source

Poly.log

fn log(self, n: Int) -> Poly<T>

The formal logarithm mod x^n (self[0] == 1), as the free log.

  • cost: O(n log n)
  • traps: as the free log: n < 0, or n > 0 with self.at(0) != 1

Examples:

  • type Z = Mod<998244353>; Poly<Z>([1, 2, 1]).log(3).at(2) == Z(-1)

Source

Poly.exp

fn exp(self, n: Int) -> Poly<T>

The formal exponential mod x^n (self[0] == 0), as the free exp.

  • cost: O(n log n)
  • traps: as the free exp: n < 0, or n > 0 with self.at(0) != 0

Examples:

  • type Z = Mod<998244353>; Poly<Z>([0, 2]).exp(3).at(2) == Z(2)

Source

Poly.pow

fn pow(self, k: Int, n: Int) -> Poly<T>

The formal power self(x)^k mod x^n, as the free pow.

  • cost: O(n log n)
  • traps: as the free pow: n < 0, or k < 0 with self.at(0) == 0

Examples:

  • type Z = Mod<998244353>; Poly<Z>([1, 1]).pow(3, 4).at(2) == Z(3)

Source

Poly.sqrt

fn sqrt(self, n: Int) -> ?Poly<T>

The formal square root mod x^n, or None, as the free sqrt.

  • cost: O(n log n + log^2 P)
  • traps: when n < 0

Examples:

  • type Z = Mod<998244353>; Poly<Z>([1, 2, 1]).sqrt(3)!.at(1) == Z(1)

Source

Poly.eval

fn eval(self, x: T) -> T

The value at x by Horner's rule.

  • cost: O(n)
  • traps: never

Examples:

  • Poly<Int>([1, 2, 3]).eval(2) == 17

Source

Poly.shift

fn shift(self, c: T) -> Poly<T>

The Taylor shift self(x + c), as taylor_shift.

  • cost: O(n log n)
  • traps: when T cannot divide by the factorials below n (n > P for Mod<P>)

Examples:

  • type Z = Mod<998244353>; Poly<Z>([0, 0, 1]).shift(Z(1)).at(1) == Z(2)

Source

Poly<T>

impl Add for Poly<T>

Source

Poly<T>.add

fn add(a, b)

Source

Poly<T>

impl Sub for Poly<T>

Source

Poly<T>.sub

fn sub(a, b)

Source

Poly<T>

impl Neg for Poly<T>

Source

Poly<T>.neg

fn neg(a)

Source

Poly<T>

impl Mul for Poly<T>

Source

Poly<T>.mul

fn mul(a, b)

Source

Poly<T>

impl Div for Poly<T>

Source

Poly<T>.div

fn div(a, b)

Source

SubproductTree

pub struct SubproductTree<P>

O(m log^2 m) build. Prebuilt product tree over points xs for multipoint evaluation, transposed evaluation, and interpolation.

Source

SubproductTree.new

fn new(xs: List<Mod<P>>, keep: Int = -1) -> SubproductTree<P>

Build the subproduct tree for the points xs: leaf i is x - xs[i] and each node the product of its children. With keep >= 0 every stored product is truncated mod x^keep, which is all eval_transposed needs; eval and interpolate need the full tree (keep < 0, the default).

  • cost: O(m log^2 m) time, O(m log m) space
  • empty: a tree over no points
  • traps: when a transform length exceeds what P supports

Examples:

  • type Z = Mod<998244353>; let xs: List<Z> = [0, 1, 2]; let t = SubproductTree(xs); t.eval([Z(1), Z(2), Z(3)]) == [Z(1), Z(6), Z(17)]

Source

SubproductTree.eval

fn eval(self, f: List<Mod<P>>) -> List<Mod<P>>

Evaluate f at every point in the tree: [f(x) for x in xs].

  • cost: O((deg f + m) log^2 m)
  • empty: [] for a tree over no points
  • order: one value per point, in xs order
  • traps: when the tree was built with keep >= 0

Examples:

  • type Z = Mod<998244353>; let xs: List<Z> = [1, 2]; SubproductTree(xs).eval([Z(0), Z(0), Z(1)]) == [Z(1), Z(4)]

Source

SubproductTree.eval_transposed

fn eval_transposed(self, c: List<Mod<P>>) -> List<Mod<P>>

Transposed multipoint evaluation (Bostan-Lecerf-Schost / Tellegen's principle): the transpose of eval on polynomials of degree < m, so out[k] = sum_i c[i] * xs[i]^k for k in 0..m.

  • cost: O(m log^2 m)
  • empty: [] for a tree over no points
  • order: by power k, increasing
  • traps: when c.len != m, or keep is in 0..m

Examples:

  • type Z = Mod<998244353>; let xs: List<Z> = [1, 2]; SubproductTree(xs).eval_transposed([Z(1), Z(1)]) == [Z(2), Z(3)]

Source

SubproductTree.interpolate

fn interpolate(self, ys: List<Mod<P>>) -> List<Mod<P>>

The unique polynomial of degree < m taking values ys at the tree's points, as exactly m coefficients. The points must be distinct.

  • cost: O(m log^2 m)
  • empty: []
  • order: lowest degree first
  • traps: when ys.len != m, two points are equal, or the tree was built with keep >= 0

Examples:

  • type Z = Mod<998244353>; let xs: List<Z> = [0, 1, 2]; SubproductTree(xs).interpolate([Z(1), Z(4), Z(9)]) == [Z(1), Z(2), Z(1)]

Source

On this page