On 3 Nov 99, at 13:53, Alex Kruppa wrote:
Ernst Mayer once mentioned to me that Prime95 needs twice the FFT size for 2^n+1
numbers (compared to 2^n+1 numbers). Does that mean that George is using the identity
2^(2n)-1 = (2^n+1)(2^n-1) ? I was wondering why ECM on 2^n+1 numbers took much
longer than on 2^n-1 of the same size..
It used to be the case that 2^n+1 was only using power-of-two FFT run
lengths. v19 has addressed this problem; I think you'll find that ECM
on 2^n+/-1 takes about the same time now (for the same n).
That would mean that I can do ECM on, for example, P773 and M773 at the same time by
doing ECM on M1546, and it will take just as long as ECM on only P773, right? When I
find a factor, I'll just have see which number it divides.
Interesting idea ... but, the algorithm being O(n log n), it _should_
take a bit longer to run a single transform with run length 2N than
it does to run two transforms each with run length N.
This is particularly relevant since there is a good chance (with
small exponents) that the FFT will run from the processor cache; if
doubling the FFT run length causes overspill into main memory, the
performance could suffer dramatically.
Regards
Brian Beesley
_
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
