Skip to Content
ReferenceLibrary

ntt

The ntt module.

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

Curved

pub enum Curved = Both | Right | Neither

Which arguments of a convolution over a semiring other than (+, *) have the shape that makes it fast: convex for min, concave for max. Neither asks for the O(n m) loop by name.

Source

Curved.Both

Both

Source

Curved.Right

Right

Source

Curved.Neither

Neither

Source

Disjoint

pub struct Disjoint

The index op of a subset convolution: i | j over disjoint pairs i & j == 0. A value with a transform impl, so user libraries can define more index ops the same way.

Source

subset

pub const subset = Disjoint()

on: subset in convolve.

Source

SosOver

pub enum SosOver = Sub | Sup

Direction of a sum-over-subsets (SOS) zeta/Mobius transform.

Source

SosOver.Sub

Sub

Source

SosOver.Sup

Sup

Source

RelaxedConvolve

pub struct RelaxedConvolve<P>

O(log^2 n) amortized per step, O(n log^2 n) total. Online (relaxed) NTT convolution: supply (a[k], b[k]) one step at a time and immediately receive c[k] = sum_{i=0..=k} a[i] * b[k - i].

Source

RelaxedConvolve.new

fn new() -> RelaxedConvolve<P>

An empty online convolution: no values pushed yet.

  • cost: O(1)
  • traps: never

Examples:

  • type Z = Mod<17>; var rc = RelaxedConvolve<17>(); rc.push(Z(0), Z(0)) == Z(0)

Source

RelaxedConvolve.push

fn push(mut self, ai: Mod<P>, bi: Mod<P>) -> Mod<P>

Append a[k] = ai and b[k] = bi at the next index k and return c[k] = sum_{i=0..=k} a[i] * b[k - i].

c[k] depends only on values already pushed, so a[k+1] and b[k+1] may be computed from it: the shape of online DP like f[k] = sum f[i] g[k - i].

  • cost: O(log^2 k) amortized
  • traps: when k reaches the largest NTT length P supports

Examples:

  • type Z = Mod<17>; var rc = RelaxedConvolve<17>(); rc.push(Z(1), Z(3)) == Z(3)
  • type Z = Mod<17>; var rc = RelaxedConvolve<17>(); rc.push(Z(1), Z(3)); rc.push(Z(2), Z(4)) == Z(10)

Source

SemiRelaxedConvolve

pub struct SemiRelaxedConvolve<P>

O(log^2 n) amortized per step. Semi-relaxed NTT convolution against a fixed b (supply a[k] online and immediately receive c[k] = sum_{i=0..=k} a[i] * b[k - i]).

Source

SemiRelaxedConvolve.new

fn new(b: List<Mod<P>>) -> SemiRelaxedConvolve<P>

An online convolution against the fixed polynomial b, nothing pushed yet.

b is zero-padded as far as the pushes go, so pushing past b.len is allowed; an empty b makes every c[k] zero.

  • cost: O(b.len)
  • empty: every pushed c[k] is zero
  • traps: never

Examples:

  • type Z = Mod<17>; var sc = SemiRelaxedConvolve<17>([Z(1), Z(2)]); sc.push(Z(1)) == Z(1)
  • type Z = Mod<17>; let e: List<Z> = []; var sc = SemiRelaxedConvolve<17>(e); sc.push(Z(5)) == Z(0)

Source

SemiRelaxedConvolve.push

fn push(mut self, ai: Mod<P>) -> Mod<P>

Append a[k] = ai at the next index k and return c[k] = sum_{i=0..=k} a[i] * b[k - i].

  • cost: O(log^2 k) amortized
  • traps: when k reaches the largest NTT length P supports

Examples:

  • type Z = Mod<17>; var sc = SemiRelaxedConvolve<17>([Z(1), Z(2)]); sc.push(Z(1)); sc.push(Z(2)); sc.push(Z(5)) == Z(9)

Source

On this page