Part IX · Number Theory, Combinatorics and Algebra
57. Polynomial Algorithms and Fast Transforms
6 lessons•24 topics•Intermediate / Expert
0 of 6 lessons published
57.01Outline
Polynomials
- Degree
- Coefficient representation
- Evaluation
- Addition/multiplication
- Convolution
57.02Outline
Fast Fourier transform
- Complex roots of unity
- Cooley-Tukey FFT
- Iterative bit reversal
- Precision errors
57.03Outline
Number theoretic transform
- NTT-friendly primes
- Primitive roots
- Inverse NTT
- Exact integer convolution
57.04Outline
Convolution applications
- Big integer multiplication
- Pair sum counts
- String matching via convolution
- Polynomial product
57.05Outline
Formal power series
- Inverse
- Derivative
- Integral
- Log/exp of series overview
57.06Outline
Transform variants
- Fast Walsh-Hadamard transform
- XOR/AND/OR convolutions
- Subset convolution overview