17 ms·
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 alg
by 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 agoThis is indeed the issue. Using provable bounds loses too many bits for complex FFTs to make sense for long multiplies.
- cperciva 3y agoI (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.