FFT boundaries

[davieddy]

Having contemplated the statistics of large numbers
(e.g. molecules in a cc of air), I find it difficult to believe
that the frequency of "floating point error exceeded 0.4"
would not increase from 5% to 95% monotonically.with the exponent.

How does that brief test that Prime95 performs before the FFT
size is settled on predict the likelihood of such an occurence?

David

[cheesehead]

George and others have conducted extensive investigations into the occurrences of floating point errors in the results of FFTs.

Also, see section 4.2.2 "Accuracy of Floating Point Arithmetic" in Knuth's The Art of Computer Programming.

[davieddy]

Originally Posted by cheesehead

George and others have conducted extensive investigations into the occurrences of floating point errors in the results of FFTs.

Also, see section 4.2.2 "Accuracy of Floating Point Arithmetic" in Knuth's The Art of Computer Programming.

I know.
Will do.

But is my gut instinct obviously wrong?

David

[CRGreathouse]

Originally Posted by davieddy

But is my gut instinct obviously wrong?

I would tend to say, "yes".

[cheesehead]

Originally Posted by davieddy

But is my gut instinct obviously wrong?

David

A fuzzy explanation:

For instance, there are guard bits. As long as a FP error is confined to the guard bits, it has zero effect on the result. So the error curve would be very low for most of a range, then at the upper end rise much faster. Monotonic, but not linear.

[Prime95]

I've observed that when you increase the number of bits stuffed into each FFT word by one, the roundoff error quadruples.

[Mr. P-1]

Originally Posted by davieddy

But is my gut instinct obviously wrong?

It's not obvious that it's wrong. Nevertheless, I'd put my trust in those who have spent years studying the matter more than I'd put it in your gut, or mine for that matter.

[davieddy]

Originally Posted by Prime95

I've observed that when you increase the number of bits stuffed into each FFT word by one, the roundoff error quadruples.

Originally Posted by Mr. P-1

It's not obvious that it's wrong. Nevertheless, I'd put my trust in those who have spent years studying the matter more than I'd put it in your gut, or mine for that matter.

THX George.
That was exactly the sort of simple empirical observation
I was seeking when I started this thread.

Does it not scream out for a simple explanation?

One bit good, 2 bits bad?

George Orwell

BTW I've been feeding my considerable gut on errors
in general and FFTs in particular for neigh on 45 years.

[cheesehead]

Originally Posted by Prime95

I've observed that when you increase the number of bits stuffed into each FFT word by one,

... which decreases the number of guard bits by one, right? ...

the roundoff error quadruples.

[davieddy]

Originally Posted by cheesehead

... which decreases the number of guard bits by one, right? ...

And when the squaring happens, by two bits.

[ewmayer]

Originally Posted by Prime95

I've observed that when you increase the number of bits stuffed into each FFT word by one, the roundoff error quadruples.

Exactly according to the model I published here (cf. equations 6 and 7, and the discussion in that section), which I use for automated runlength-setting in Mlucas.

Note that the above heuristics work with FFT+DWT computations, but only if the DWT weights are (real or complex) of order unity. Mersenne and Fermat-mod DWT both satisfy this criterion.