FFT boundaries
 

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

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 [i]The Art of Computer Programming[/i].

[QUOTE=cheesehead;258849]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 [I]The Art of Computer Programming[/I].[/QUOTE]

I know.
Will do.

But is my gut instinct obviously wrong?

David

[QUOTE=davieddy;258854]But is my gut instinct obviously wrong?[/QUOTE]

I would tend to say, "yes".

[QUOTE=davieddy;258854]
But is my gut instinct obviously wrong?

David[/QUOTE]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.

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

[QUOTE=davieddy;258854]But is my gut instinct obviously wrong?[/QUOTE]

It's not [i]obvious[/i] 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.

From the horse's gut
 

[QUOTE=Prime95;258950]I've observed that when you increase the number of bits stuffed into each FFT word by one, the roundoff error quadruples.[/QUOTE]

[QUOTE=Mr. P-1;258954]It's not [I]obvious[/I] 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.[/QUOTE]

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.

[QUOTE=Prime95;258950]I've observed that when you increase the number of bits stuffed into each FFT word by one,[/quote]... which decreases the number of guard bits by one, right? ...
[quote]the roundoff error quadruples.[/QUOTE]

[QUOTE=cheesehead;259052]... which decreases the number of guard bits by one, right? ...[/QUOTE]
And when the squaring happens, by two bits.

[QUOTE=Prime95;258950]I've observed that when you increase the number of bits stuffed into each FFT word by one, the roundoff error quadruples.[/QUOTE]

Exactly according to the model I published [url=http://www.mersenneforum.org/attachments/pdfs/F24.pdf]here[/url] (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.