5 ms·

Something that always bothers me about these explanations is they usually forget about numerical errors. You can't just abstract away multiplying coefficients a

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.html http://numbers.computation.free.fr/Constants/Algorithms/fft....

e-khadem 2y ago
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.
- xphos 2y ago
  Had no clue what NTT was but found this as a reference https://codeforces.com/blog/entry/48798#:~:text=NTT%20(Number%20Theoretic%20Transform),calculations%20are%20done%20in%20integers https://codeforces.com/blog/entry/48798#:~:text=NTT%20(Numbe....
  - programjames 2y ago
    I prefer this reference: https://cp-algorithms.com/algebra/fft.html#number-theoretic-transform https://cp-algorithms.com/algebra/fft.html#number-theoretic-...
  - dataflow 2y ago
    See chapter 26 of the "FXT book". I just shared it here: https://news.ycombinator.com/item?id=40841355 https://news.ycombinator.com/item?id=40841355
- programjames 2y ago
  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.
  - adgjlsfhk1 2y ago
    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.
  - archgoon 2y ago
    > 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.
cperciva 2y ago
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).
- dataflow 2y ago
  Would you mind just sharing it here...?
  - cperciva 2y ago
    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 https://www.daemonology.net/papers/fft.pdf
    - eranation 2y ago
      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.
      - cperciva 2y ago
        Knuth judged that it wasn't an erratum, since the bound he included was correct and he never claimed it was optimal. :-/
        Randor 2y ago
        Thanks, not often we see Knuth erratas. :)
        cperciva 2y ago
        <pedant>You never see "erratas", since "errata" is already the plural (of "erratum").</pedant>
uoaei 2y ago
Hence the distinction between computer science and software engineering. :)
teleforce 2y ago
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 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 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 https://arxiv.org/abs/2307.01836

e-khadem 2y ago

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.

xphos 2y ago
Had no clue what NTT was but found this as a reference https://codeforces.com/blog/entry/48798#:~:text=NTT%20(Number%20Theoretic%20Transform),calculations%20are%20done%20in%20integers https://codeforces.com/blog/entry/48798#:~:text=NTT%20(Numbe....
- programjames 2y ago
  I prefer this reference: https://cp-algorithms.com/algebra/fft.html#number-theoretic-transform https://cp-algorithms.com/algebra/fft.html#number-theoretic-...
- dataflow 2y ago
  See chapter 26 of the "FXT book". I just shared it here: https://news.ycombinator.com/item?id=40841355 https://news.ycombinator.com/item?id=40841355
programjames 2y ago
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.
- adgjlsfhk1 2y ago
  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.
- archgoon 2y ago
  > 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.

cperciva 2y ago

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

dataflow 2y ago
Would you mind just sharing it here...?
- cperciva 2y ago
  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 https://www.daemonology.net/papers/fft.pdf
  - eranation 2y ago
    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.
    - cperciva 2y ago
      Knuth judged that it wasn't an erratum, since the bound he included was correct and he never claimed it was optimal. :-/
      - Randor 2y ago
        Thanks, not often we see Knuth erratas. :)
        cperciva 2y ago
        <pedant>You never see "erratas", since "errata" is already the plural (of "erratum").</pedant>

uoaei 2y ago

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

teleforce 2y ago

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 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 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 https://arxiv.org/abs/2307.01836