Re:Discrete Fourier Transform
by throw_away_8080 on Sunday October 05, 2025 @01:03AM
(#45478971)
If you wanted to multiply two polynomials f and g of degree n, you could do distribution and the do n squared multiplications. Instead, evaluate the two separate polynomials at 2n special points, multiply the results pointwise, and then interpolate. The magical part is there are some specific points which speed up the evaluation and interpolation steps using a divide and conquer type algorithm.
[ Parent
| on HN ]
There are no comments on this comment yet.