Hi all,
I'm working on version 19 of prime95 and I need your help.
In the past, the exponents at which a larger FFT is used was picked
rather haphazardly. I simply picked a few exponents trying to find
one that could run a thousand or so iterations without the convolution
error greatly exceeding 0.3.
For this release, I thought it would be nice to use a more
scientific approach. What I've done is run almost 10000 iterations
of an exponent and used Excel to graph the number of iterations with
an error between 0.200 and 0.201, 0.201 and 0.202, etc. As you can imagine
you get a Bell-like curve that peaks at some value.
Since it has been 25 years since I took statistics courses
in college, I am at a loss as to how to use this graph to predict the
probability that N iterations will have an error below M. I could
then use such information to find the exponent such that the chance
of a convolution error exceeding 0.5 is less than 1 in 10^40 (or some
other criteria that we agree is "safe").
Rather than mail these largish spreadsheets to the entire list,
two sample graphs are at ftp://entropia.com/gimps/x1345000.xls and
ftp://entropia.com/gimps/x1360000.xls (in the graphs a 400 on the X-axis
is really a convolution error of 0.400, the Y-axis is a count of iterations).
Any help is appreciated.
Best regards,
George
P.S. A brief explanation of convolution errors: Since the FFT in prime95
is done in floating point arithmetic, round-off errors build up. After the
FFT, every value is rounded back to an integer. The convolution error is
the largest amount that a result value differs from the correct integer
value. If the convolution error exceeds 0.5, then the round-back-to-integer
step will round to the wrong integer value - a catastrophic failure.
Another way to look at this: Each FFT value contains about 20 bits of data.
That is, values ranging from 2^19 to -2^19. Consider an FFT of 128K elements.
If each FFT value was close to the 2^19 value, then each result value would
need 19+19+17=55 bits to hold the result. Since a float only holds 53 bits
there would be a loss of information. Fortunately, probability assures us
that it is extremely unlikely that every (or even most) FFT values will
be close to the 2^19 maximum value.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
