View Single Post
Old 2006-08-08, 04:08   #5
drew's Avatar
Jun 2005

38210 Posts

Originally Posted by ewmayer
A more precise estimate, which also shows how the accuracy decreases (quite slowly though) with increasing FFT length can be found here - two out of three authors of that paper have posted to this thread, so hey, it must be true. ;)
That's why I came here to ask.

FWIW, I switched to a balanced-digit representation, and now it works through 2^22, at least when testing the primes M11213, M21701, M44497 and M86243.

I now understand the cause of that limit...the depth of the FFT requires more additions of values, and I had been thinking in terms of decimal, not binary digits when I said it should only account for a couple of digits of precision. I expect that the loss of precision should grow *much* more slowly beyond the numbers I've already tested (up to the 34th Mersenne prime).

My next optimization will be to convert to a real-valued FFT, hopefully cutting the FFT size for most exponents in half, but since the data will be twice as dense, I expect to lose that bit I gained going to the balanced-digit representation.


Last fiddled with by drew on 2006-08-08 at 04:18
drew is offline   Reply With Quote