Opening Fast Fourier Transform (FFT) and Integer Multiplication
Fast Fourier Transform (FFT) and Integer Multiplication
- Length
- 26 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Before the lecture
The Fast Fourier Transform computes the discrete Fourier transform in operations and completes the reduction of integer multiplication to polynomial multiplication. O'Donnell first proves the Fourier matrix has orthogonal columns, each with squared norm , so its inverse is the same matrix with negated exponents, scaled by . A divide-and-conquer algorithm then splits a size- transform into two half-size transforms plus linear work, giving the merge-sort recurrence . The final part turns to the word RAM model, citing Knuth's The Art of Computer Programming. With bits of precision, rounding the complex output recovers the exact integer product.

Your comment is kept while you sign up.Sign in
O'Donnell halves the discrete Fourier transform recursively and shows bits of precision suffice.
The Fast Fourier Transform computes the discrete Fourier transform in operations and completes the reduction of integer multiplication to polynomial multiplication. O'Donnell first proves the Fourier matrix has orthogonal columns, each with squared norm , so its inverse is the same matrix with negated exponents, scaled by . A divide-and-conquer algorithm then splits a size- transform into two half-size transforms plus linear work, giving the merge-sort recurrence T(N) = 2T(N/2) + O(N). The final part turns to the word RAM model, citing Knuth's The Art of Computer Programming. With bits of precision, rounding the complex output recovers the exact integer product.
The Art of Computer Programming
This lecture
Lecture 20 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.