Faster Fourier Transform
by John from John D. Cook on (#78XAK)
The Fast Fourier Transform (FFT) algorithm can compute the discrete Fourier transform of a sequence of lengthn in time
O(n logn).
OpenAI recently posted a paper saying there is an algorithm that could compute the discrete Fourier transform in
O(n (logn)1 - )
time for = 10-13.
This result is amazing. It seemed that O(n logn) was as good as you could do, which it provably is for sorting algorithms.
The result is also of absolutely no practical value, for now. But since the theorem shows that our assumptions were wrong, however slightly, about what is possible, maybe we're in for further surprises. Maybe the crack will grow. It wouldn't be the first time.
Related postsThe post Faster Fourier Transform first appeared on John D. Cook.