Intuition, Vocabulary and Foundations
A polynomial is stored by coefficients, $A(x)=\sum_i a_ix^i\leftrightarrow[a_0,a_1,\ldots]$. Multiplication is convolution:
$$c_k=\sum_{i=0}^{k}a_i b_{k-i}.$$
Thus $(1+2x+3x^2)(4+5x)=4+13x+22x^2+15x^3$. Naive multiplication costs $O(nm)$. FFT and NTT instead evaluate at roots of unity, multiply pointwise, and interpolate. FFT uses approximate complex arithmetic; NTT uses exact finite-field arithmetic. A primitive $N$th root $\omega$ satisfies $\omega^N=1$ but $\omega^j\ne1$ for $0\lt j\lt N$.
Formal power series treat coefficients algebraically to a declared precision. An inverse $G=F^{-1}\bmod x^n$ requires invertible $f_0$; the standard formal logarithm requires $f_0=1$.
Fast convolution is evaluation, pointwise multiplication, and interpolation, but zero-padding is part of correctness. Choose a supported transform length at least $\deg A+\deg B+1$ so the cyclic transform represents the desired linear convolution.
| Concept | Definition | Example | Boundary | Question answered |
|---|---|---|---|---|
| Convolution | $c_k=\sum_i a_i b_{k-i}$ | $[1,2]*[3,4]=[3,10,8]$ | Pointwise products are different | How are product coefficients formed? |
| Root of unity | Primitive $\omega$ with $\omega^N=1$ | Power-of-two NTT root | Lower-order roots lose information | Which evaluation grid is invertible? |
| FFT | Complex transform | Rounded integer convolution | Floating error may corrupt coefficients | How is approximate convolution accelerated? |
| NTT | Finite-field transform | Modulo $998244353$ | Length must divide $p-1$ | How is modular convolution exact? |
| Formal inverse | $FG\equiv1\pmod{x^n}$ | $(1-x)^{-1}=1+x+\cdots$ | Requires invertible $f_0$ | How is series division defined? |
| Formal logarithm | $\log F=\int F'/F$ | $\log(1+x)$ | Standard form requires $F(0)=1$ | How are products linearized? |
Step-by-Step Derivations and Algorithms
For input lengths $n,m$, choose the smallest supported power of two $N\ge n+m-1$, pad with zeros, transform both arrays, multiply corresponding values, and invert. A radix-two transform splits even and odd coefficients and combines them through butterfly equations.
For NTT modulus $p$, the length must divide $p-1$. The inverse uses reciprocal roots and multiplication by $N^{-1}$. Wide exact integer convolution uses several NTT primes and CRT; their product must exceed the proven coefficient range.
Newton inversion doubles precision:
$$G_{\mathrm{new}}=G(2-FG)\pmod{x^{2m}}.$$
If $FG=1-E$ modulo $x^m$, then $FG_{\mathrm{new}}=1-E^2$, so the error begins at degree $2m$. From inversion follow $\log F=\int F'/F$ and exponential via $G_{\mathrm{new}}=G(1+F-\log G)$.
flowchart TD
A["Choose coefficient domain and precision"] --> B{"Operation?"}
B -->|"Convolution"| C["Pad to supported length"]
C --> D{"FFT or NTT?"}
D -->|"FFT"| E["Control rounding"]
D -->|"NTT"| F["Validate prime and root order"]
E --> G["Transform, multiply, invert"]
F --> G
B -->|"Formal series"| H["Check constant term"]
H --> I["Newton precision doubling"]
G --> J["Normalize and truncate"]
I --> J
Each butterfly preserves evaluation on the current root grid, and the inverse restores coefficients after scaling by $N^{-1}$. FFT and NTT cost $O(N\log N)$; Newton iteration reaches precision $n$ in $O(M(n))$ when multiplication costs $M(n)$.
Implementation, Complexity and Engineering
This reference uses $998244353=119\cdot2^{23}+1$ and primitive root $3$. It validates lengths, normalizes coefficients, implements exact convolution, and builds derivative, integral, inverse, and logarithm operations.
| Method | Domain | Time | Advantage | Failure mode | Mitigation |
|---|---|---|---|---|---|
| Naive convolution | Any ring | $O(nm)$ | Simple exact oracle | Quadratic runtime | Use for small cases and tests |
| Complex FFT | Floating point | $O(N\log N)$ | Flexible lengths | Rounding corruption | Bound error and verify |
| Single NTT | Supported finite field | $O(N\log N)$ | Exact modular result | Unsupported length | Validate modulus and root order |
| Multiple NTT plus CRT | Several primes | $O(tN\log N)$ | Wide exact integers | Prime product too small | Prove coefficient bounds |
| Newton inverse | Suitable field | $O(M(n))$ | Doubles precision | Noninvertible constant | Check $f_0$ first |
| FPS logarithm | Field with index inverses | $O(M(n))$ | Turns products into sums | Wrong constant term | Normalize or reject |
Applications, Case Studies and Exercises
Convolution combines independent counts, accelerates large-integer multiplication, correlation, probability distributions, and many dynamic programs. Formal series turn algebraic specifications into coefficient algorithms, but every operation needs explicit precision and domain preconditions.
Apply Polynomial Algorithms, FFT & NTT
Pair-sum distribution: convolve two six-sided-die coefficient arrays. Confirm the coefficient of $x^7$ is $6$, the coefficient sum is $36$, and the result is symmetric.
Large histogram merge: convolve lengths $200{,}000$ and $150{,}000$. Choose the smallest supported power of two at least $349{,}999$, compare random coefficients with direct sums, and use extra primes plus CRT if exact coefficients can exceed the modulus.
Hands-on series engine: implement inverse, logarithm, and exponential. Verify $FF^{-1}\equiv1$, $\exp(\log F)\equiv F$ for $F(0)=1$, and $\log(\exp G)\equiv G$ for $G(0)=0$, all modulo $x^n$. Differentially test through $n=64$.
Exercises: multiply two small polynomials manually; explain cyclic wraparound; derive butterflies; prove Newton doubling; find the maximum supported transform length; implement three-prime CRT; add formal square roots with documented preconditions.
Use naive multiplication for small inputs, FFT when controlled approximation is acceptable, NTT for exact modular convolution, and multiple primes plus CRT for wider integers. Formal-series operations require explicit precision, valid constant terms, normalization, and independent verification.
Next in the Series
In Finite Fields & Polynomial Factorization, we'll explore Compute in prime and extension fields using polynomial quotients..