Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

You're essentially describing a residue number system, except the different moduli need to be coprime for things to be well-defined.

FFT multiplication is basically a residue number system product on polynomials. Evaluating a polynomial p(x) at a point w_i is the same as computing p(x) modulo (x - w_i), where w_i here is one of the nth roots of unity. So the FFT computes p(x) mod (x - w_0), p(x) mod (x - w_1), ..., multiplies each residue individually, and the inverse FFT recovers the result modulo (x - w_0)(x - w_1)...(x - w_{n-1}) = x^n - 1.



Thank you!




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: