← Back to context Comment by xyzzyz 1 day ago They also separately give algorithm for Fourier transform over complex number faster than O(n log n) 4 comments xyzzyz Reply saalweachter 1 day ago Wikipedia just told me there's a galactic algorithm for integer multiplication in O(n log n) based on FFT so I'm guessing those two proofs are related. pfdietz 19 hours ago Multiplication is a lot like convolution, so the connection is natural. rubikscube09 18 hours ago multiplication is implemented w the fft 1 reply →
saalweachter 1 day ago Wikipedia just told me there's a galactic algorithm for integer multiplication in O(n log n) based on FFT so I'm guessing those two proofs are related. pfdietz 19 hours ago Multiplication is a lot like convolution, so the connection is natural. rubikscube09 18 hours ago multiplication is implemented w the fft 1 reply →
pfdietz 19 hours ago Multiplication is a lot like convolution, so the connection is natural. rubikscube09 18 hours ago multiplication is implemented w the fft 1 reply →
Wikipedia just told me there's a galactic algorithm for integer multiplication in O(n log n) based on FFT so I'm guessing those two proofs are related.
Multiplication is a lot like convolution, so the connection is natural.
multiplication is implemented w the fft
1 reply →