- Eval a polynomical A(x) at x0 : Horner’s rule
- Mutlply two polys:
- Closed form at O(n^2) naively -> O(nlogn) possible
- Equivalent to convolution of vectors A * reverse(B) - inner products of all possible shifts
- Poly representations:
- Samples for n points with all distince xs.
- Convert between this and coefficient form in O(nlogn)
- Sampling n points takes O(n^2) in total
- A sequence of n roots
- Eval A(x) for x in X: D&C by even/odd i
- A(x) = A_even(x^2) + x * A_odd(x^2)
- Derive the recursion and cost => draw the recursion tree and we see it is still n^2
- Square a number on the unit circle on the complex plane
- FFT is the d&c algo for DFT (coefficent to sample form)
- Fast poly multiplicatin: FFT(A) * FFA(B) and then do inverse FFT
- Similar techique