Hacker News Reader

Comment by programjames | Hacker News Reader

Something that always bothers me about these explanations is they usually forget about numerical errors. You can't just abstract away multiplying coefficients as "constant time". You may as well abstract away the entire multiplication to begin with! If you take into account numerical precision, it's closer to O(n (log n)^3) [1].

[1]: http://numbers.computation.free.fr/Constants/Algorithms/fft....

View on HN

The error bound cited in that article is wildly pessimistic. The latest edition of Knuth has the correct bound (because I gave it to him).

Would you mind just sharing it here...?

Short 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

This 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.

Knuth judged that it wasn't an erratum, since the bound he included was correct and he never claimed it was optimal. :-/

Thanks, not often we see Knuth erratas. :)

<pedant>You never see "erratas", since "errata" is already the plural (of "erratum").</pedant>

The ensemble of errata of multiple books are erratas… probably.

Did he decide to include your better bound in future editions?

Yes. I believe proving the strict bound is one of the exercises now.

For 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

[2]: https://www.texmacs.org/joris/nlogn/nlogn-abs.html

It will be great if we can minimize the multiplication errors and perhaps do away with the errors altogether by utilizing quaternion based operations describes in the OP article [1],[2],[3].

[1] One-Dimensional Quaternion Discrete Fourier Transform and an Approach to Its Fast Computation:

https://www.mdpi.com/2079-9292/12/24/4974

[2] Convolution Theorems for Quaternion Fourier Transform: Properties and Applications:

https://onlinelibrary.wiley.com/doi/10.1155/2013/162769

[3] On the Matrix Form of the Quaternion Fourier Transform and Quaternion Convolution:

https://arxiv.org/abs/2307.01836

But if the coefficients are integers, you can use NTT with a big enough modulus and get exact results and a boost (esp. in hardware) in multiplication time.

Had no clue what NTT was but found this as a reference https://codeforces.com/blog/entry/48798#:~:text=NTT%20(Numbe....

I prefer this reference: https://cp-algorithms.com/algebra/fft.html#number-theoretic-...

See chapter 26 of the "FXT book". I just shared it here: https://news.ycombinator.com/item?id=40841355

Is there a way to find groups with easy generators/primitive roots? I imagine you'd want a small root of unity, but also be able to choose a bigger modulus for extra big multiplications. Also, afaik it's discrete-logarithm level of difficulty to even find a generator if you choose a random modulus, though I don't know if it's easier to find a modulus after you choose the generator.

since the groups you're looking at are is size log(n), you can do a lot of work without issue. as long as you do experimental it less work, it doesn't affect the runtime.

> though I don't know if it's easier to find a modulus after you choose the generator.

Sure, pick a large prime. Double it and add 1 (and call it n). If it's still prime, then you know the prime factorization of n-1. Pick your generator, and check if it raised to the p is 1, or if squaring it is one. If not, it's a generator of the multiplicative group mod n.

Hence the distinction between computer science and software engineering. :)

Reply on news.ycombinator.com