Module discrete 

Discrete transforms on exact sequences (convolution, NTT, Walsh–Hadamard, Möbius). Discrete transforms on exact sequences (SymPy’s sympy.discrete): linear, cyclic and subset convolutions, the number-theoretic transform, the Walsh–Hadamard transform and the Möbius (subset/superset-sum) transform. (0.9)

Everything here is exact. Sequences are Ratio<BigInt> (or BigInt residues for the NTT) and every result is an exact rational or residue. There is deliberately no floating-point FFT (sympy.discrete.transforms.fft) and no symbolic DFT over Ex roots of unity: the exact tool for polynomial multiplication is convolution (or convolution_ntt modulo a prime), and a symbolic result is obtained by mapping the rationals through Context::from_ratio or by using convolution_ex directly on Ex coefficients.

Transforms that need a power-of-two length (ntt, fwht, mobius_transform and their inverses, convolution_subset) zero-pad their input to the next power of two, exactly as SymPy does; the empty sequence is returned unchanged.

Examples

use symplex::discrete::{convolution, fwht, ifwht, mobius_transform};
use num_bigint::BigInt;
use num_rational::Ratio;

let q = |v: &[i64]| -> Vec<Ratio<BigInt>> {
    v.iter().map(|&t| Ratio::from_integer(BigInt::from(t))).collect()
};
// (1 + 2x + 3x²)(4 + 5x + 6x²) = 4 + 13x + 28x² + 27x³ + 18x⁴
assert_eq!(convolution(&q(&[1, 2, 3]), &q(&[4, 5, 6])), q(&[4, 13, 28, 27, 18]));
assert_eq!(fwht(&q(&[1, 2, 3, 4])), q(&[10, -2, -4, 0]));
assert_eq!(ifwht(&fwht(&q(&[1, 2, 3, 4]))), q(&[1, 2, 3, 4]));
assert_eq!(mobius_transform(&q(&[1, 2, 3, 4])), q(&[1, 3, 4, 10]));

Functions

convolution

Linear convolution c[k] = Σᵢ a[i]·b[k−i] (SymPy convolution(a, b)): the coefficients of the product of the polynomials with coefficient lists a and b (index = degree).

convolution_cyclic

Cyclic convolution of length n (SymPy convolution(a, b, cycle=n)): the linear convolution folded modulo n, c[k] = Σ_{i ≡ k (mod n)} lin[i].

convolution_ex

Linear convolution of symbolic coefficient lists: c[k] = Σᵢ a[i]·b[k−i] as Ex (the coefficients of the product of two polynomials given by their Ex coefficients). Empty if either input is empty.

convolution_ntt

Linear convolution modulo a prime through the NTT (SymPy convolution(a, b, prime=p) / convolution_ntt): ntt both inputs at a power-of-two length ≥ |a| + |b| − 1, multiply pointwise, intt.

convolution_subset

Subset convolution (SymPy convolution_subset): indices are bitmasks and c[k] = Σ_{s ⊆ k} a[s]·b[k ∖ s] — the sum over all ways of writing k as a disjoint union of two subsets.

fwht

Walsh–Hadamard transform (SymPy fwht), Hadamard ordering: A[k] = Σⱼ (−1)^{popcount(j & k)} a[j]. The input is zero-padded to a power of two.

ifwht

Inverse Walsh–Hadamard transform (SymPy ifwht): fwht divided by the (padded) length, so ifwht(fwht(a)) == a for a power-of-two length.

intt

Inverse number-theoretic transform (SymPy intt): a[j] = n⁻¹·Σₖ A[k]·ω⁻ʲᵏ mod p, so that intt(ntt(a)) == a for a power-of-two length.

inverse_mobius_transform

Inverse of mobius_transform (SymPy inverse_mobius_transform(seq)): recovers a from its subset sums, a[k] = Σ_{s ⊆ k} (−1)^{|k∖s|} A[s].

inverse_mobius_transform_superset

Inverse of mobius_transform_superset (SymPy inverse_mobius_transform(seq, subset=False)).

mobius_transform

Möbius transform over subsets (SymPy mobius_transform(seq) with subset=True): indices are bitmasks and A[k] = Σ_{s ⊆ k} a[s]. The input is zero-padded to a power of two.

mobius_transform_superset

Möbius transform over supersets (SymPy mobius_transform(seq, subset=False)): A[k] = Σ_{s ⊇ k} a[s] over the padded index range.

ntt

Number-theoretic transform (SymPy ntt): the discrete Fourier transform of a over ℤ/pℤ, A[k] = Σⱼ a[j]·ωʲᵏ mod p, with ω = g^{(p−1)/n} for the smallest primitive root g (the same root SymPy uses, so the outputs agree entry for entry).