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
