6 ms·
Would you mind just sharing it here...?
by dataflow 2y ago
Would you mind just sharing it here...?
- cperciva 2y agoShort answer is that FFTs are about as well behaved as anything can possibly be, because they're rotations in C^n. Explicit bound is in https://www.daemonology.net/papers/fft.pdf https://www.daemonology.net/papers/fft.pdf
- eranation 2y agoThis is why I keep coming back to HN. You read an interesting article, a little proud you understand half of it, read a question that already makes you feel like the stupidest person in the room, then read a clarifying answer by someone who probably got a Knuth reward check for correcting an errata in the art of computer programming.
- cperciva 2y agoKnuth judged that it wasn't an erratum, since the bound he included was correct and he never claimed it was optimal. :-/
- Randor 2y agoThanks, not often we see Knuth erratas. :)
- nextaccountic 2y agoDid he decide to include your better bound in future editions?
- cperciva 2y agoYes. I believe proving the strict bound is one of the exercises now.
- guyomes 2y agoFor FFT with floating-point numbers, another paper from Arnold Schönhage in 1982 [1] already gives the bound in Psi(n l) operations, where n is the number of coefficients, and l is the desired precision (typically 53 for double precision). Psi(m) is the time to multiply two integers with m digits, which is known since 2021 to be O(m log m) [2]. So the current bound is O(nl log(nl)). [1]: https://doi.org/10.1007/3-540-11607-9_1 https://doi.org/10.1007/3-540-11607-9_1 [2]: https://www.texmacs.org/joris/nlogn/nlogn-abs.html https://www.texmacs.org/joris/nlogn/nlogn-abs.html