3 ms·

It is difficult to prove that round-off error won't affect the results. Colin Percival, Rapid multiplication modulo the sum and difference of highly composite

It is difficult to prove that round-off error won't affect the results. Colin Percival, Rapid multiplication modulo the sum and difference of highly composite numbers, Mathematics of Computation, Volume 72, Number 241, Pages 387-395, 2002.

Strilanc 3y ago
from google scholar search: https://www.ams.org/journals/mcom/2003-72-241/S0025-5718-02-01419-9/S0025-5718-02-01419-9.pdf https://www.ams.org/journals/mcom/2003-72-241/S0025-5718-02-...
- cperciva 3y ago
  Right, I didn't think people would actually want to read the paper; I just wanted to make the point that, rather than being difficult, this was solved over 20 years ago. (And I was an undergrad at the time!)
  - CodesInChaos 3y ago
    The article claims that the provable bounds for rounding errors are significantly worse than the empirical bounds used by y-cruncher, so an provably correct algorithm would not have competitive performance. I'm not sure if you claim that the bounds proven in your paper are tight enough to be competitive, or if you simply confirm that there are slower conservative implementations that are provably correct.
    - fdej 3y ago
      This is indeed the issue. Using provable bounds loses too many bits for complex FFTs to make sense for long multiplies.
    - cperciva 3y ago
      I (a) proved bounds, and (b) showed that those bounds were tight by constructing inputs which came close to the error bounds. The "empirical bounds" demonstrably don't work for some inputs.
moonchild 3y ago
I'm not familiar with the domain, but is there a particular reason for using floating-point numbers other than that they have faster hardware support? It is not hard to synthesise a fast integer multiply from a float fma, and then the rest of the algorithm can be phrased in terms of that.
- cperciva 3y ago
  Doing an FFT with integer math means doing it in a ring -- and thus dealing with modular reduction. Using complex floating-point math the "modular reduction" comes for free thanks to w^N=1. I would have to write some code to confirm which is faster today -- especially if you choose rings which make the modular reduction easier -- but CPUs have typically optimized FP math more for throughout than integer math, since mostly-integer code has more unpredictable branches and less ILP than FP-heavy code.

Strilanc 3y ago

from google scholar search: https://www.ams.org/journals/mcom/2003-72-241/S0025-5718-02-01419-9/S0025-5718-02-01419-9.pdf https://www.ams.org/journals/mcom/2003-72-241/S0025-5718-02-...

cperciva 3y ago
Right, I didn't think people would actually want to read the paper; I just wanted to make the point that, rather than being difficult, this was solved over 20 years ago. (And I was an undergrad at the time!)
- CodesInChaos 3y ago
  The article claims that the provable bounds for rounding errors are significantly worse than the empirical bounds used by y-cruncher, so an provably correct algorithm would not have competitive performance. I'm not sure if you claim that the bounds proven in your paper are tight enough to be competitive, or if you simply confirm that there are slower conservative implementations that are provably correct.
  - fdej 3y ago
    This is indeed the issue. Using provable bounds loses too many bits for complex FFTs to make sense for long multiplies.
  - cperciva 3y ago
    I (a) proved bounds, and (b) showed that those bounds were tight by constructing inputs which came close to the error bounds. The "empirical bounds" demonstrably don't work for some inputs.

moonchild 3y ago

I'm not familiar with the domain, but is there a particular reason for using floating-point numbers other than that they have faster hardware support? It is not hard to synthesise a fast integer multiply from a float fma, and then the rest of the algorithm can be phrased in terms of that.

cperciva 3y ago
Doing an FFT with integer math means doing it in a ring -- and thus dealing with modular reduction. Using complex floating-point math the "modular reduction" comes for free thanks to w^N=1. I would have to write some code to confirm which is faster today -- especially if you choose rings which make the modular reduction easier -- but CPUs have typically optimized FP math more for throughout than integer math, since mostly-integer code has more unpredictable branches and less ILP than FP-heavy code.