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).
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
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
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
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
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
Poly.len
fn len(self) -> IntThe number of stored coefficients, trailing zeros included.
- cost: O(1)
- traps: never
Examples:
Poly<Int>([1, 0]).len == 2
Poly.deg
fn deg(self) -> IntThe 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() == 1Poly<Int>([0, 0]).deg() == -1
Poly.is_zero
fn is_zero(self) -> BoolWhether 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()
Poly.at
fn at(self, i: Int) -> TRead 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
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
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
Poly.integral
fn integral(self) -> Poly<T>The formal integral with zero constant term, as the free integral.
- cost: O(n)
- traps: when
Tcannot divide by somekin1..=n(n >= PforMod<P>)
Examples:
type Z = Mod<998244353>; Poly<Z>([1, 2, 3]).integral().at(3) == Z(1)
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 == 3Poly<Int>([1, 2, 3, 4]).transposed_mul(Poly<Int>([1, 1])).at(2) == 7
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 == 2Poly<Int>([1]).truncated(3).at(2) == 0
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, orn > 0withself.at(0) == 0
Examples:
type Z = Mod<998244353>; Poly<Z>([1, -1]).inv(3).at(2) == Z(1)
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, orn > 0withself.at(0) != 1
Examples:
type Z = Mod<998244353>; Poly<Z>([1, 2, 1]).log(3).at(2) == Z(-1)
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, orn > 0withself.at(0) != 0
Examples:
type Z = Mod<998244353>; Poly<Z>([0, 2]).exp(3).at(2) == Z(2)
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, ork < 0withself.at(0) == 0
Examples:
type Z = Mod<998244353>; Poly<Z>([1, 1]).pow(3, 4).at(2) == Z(3)
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)
Poly.eval
fn eval(self, x: T) -> TThe value at x by Horner's rule.
- cost: O(n)
- traps: never
Examples:
Poly<Int>([1, 2, 3]).eval(2) == 17
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
Tcannot divide by the factorials belown(n > PforMod<P>)
Examples:
type Z = Mod<998244353>; Poly<Z>([0, 0, 1]).shift(Z(1)).at(1) == Z(2)
Poly<T>
impl Add for Poly<T>Poly<T>.add
fn add(a, b)Poly<T>
impl Sub for Poly<T>Poly<T>.sub
fn sub(a, b)Poly<T>
impl Neg for Poly<T>Poly<T>.neg
fn neg(a)Poly<T>
impl Mul for Poly<T>Poly<T>.mul
fn mul(a, b)Poly<T>
impl Div for Poly<T>Poly<T>.div
fn div(a, b)SubproductTree
pub struct SubproductTree<P>O(m log^2 m) build. Prebuilt product tree over points xs for multipoint evaluation,
transposed evaluation, and interpolation.
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
Psupports
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)]
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
xsorder - 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)]
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, orkeepis in0..m
Examples:
type Z = Mod<998244353>; let xs: List<Z> = [1, 2]; SubproductTree(xs).eval_transposed([Z(1), Z(1)]) == [Z(2), Z(3)]
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 withkeep >= 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)]