I think I can now pull this thread together. On 25th Oct Brian Beesley wrote: > On Wednesday 25 October 2006 15:36, david eddy wrote: > > The important reason a LL-test goes wrong is due to > > using floating point FFT to perform exact integer arithmetic. > > Certainly this is an important reason - and it's the one which we _can_ > target > by adjusting cut-off points etc. in the software.
> > As I am currently doing a double check I am interested in how the > > probability of an erroneous LL test varies as we go from the bottom > > to the top of the range of exponents for a given FFT size. > > A quick scan of the bad.txt database file shows that there is a significant > error rate even at the low end of the exponent range for many of the FFT run > lengths. Note that run length cutoffs vary with program & processor version > so a proper check would be difficult to impossible. > > The probability at the top of the range is presumably such that the cost > > in time of an erroneous LL test balances the extra time needed for the > > next FFT size, for which the chance of error is small. > > I think (and hope) the default setup is a bit more conservative than that. > There's the unfortunate possibility of someone running a first LL test on an > exponent and incorrectly finding it composite due to an avoidable error - we > want this to be "reasonably improbable" even though double-checking would > eventually find the mistake! On the other hand, the excerpts from you and George which Steinar dug up suggest that you were indeed trying to fix the boundaries at the point where probability of roundoff error equalled the percentage time increase incurred by using the next size of FFT. Here is how I think the risk of roundoff error varies over the range: The cut off points are such that there is a mixture of 20 bit and 19 bit integer elements. There is neglible risk of the 19 bit elements overflowing. The overall risk increases in proportion to the number of 20 bit elements. So for the 896K FFT, there is neglible risk of roundoff error from 15,300,000 to 17,432,579 (all elements 19 bits). The risk then increases linearly to the cutoff at 17,850,000 as more 20 bit elements are needed. A 12% time increase is incurred for a 1024K FFT. If this is the risk at the cutoff, the average risk over the range is ~ 1%. David Eddy _________________________________________________________________ Be one of the first to try Windows Live Mail. http://ideas.live.com/programpage.aspx?versionId=5d21c51a-b161-4314-9b0e-4911fb2b2e6d _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
