Hi,
At 07:47 AM 4/20/00 -0400, David Campeau wrote:
>Seeing that not every time a stage 1 gcd will result in a factor found, are
>we not better to wait until the end of stage 2? This way, we could factor
>deeper.
Brian Beesley's timings showed that running the Stage 1 GCD will
save time in the long run for exponents above 4 or 5 million.
>Perhaps this could be yet another option?
It is an option. Set Stage1GCD=0 in prime.ini.
>some preleminary data (on my machine at home):
>Total P-1 test = 91
>Stage 1 factor = 2
>Stage 2 factor = 1
>
>So on my machine the stage 1 gcd saved me 2 stage 2, so about 2 hour of cpu,
>but at the cost of about 90 * 230 sec of stage 1 gcd = 20700sec or 5:45
>hours. Seems to me that we could save a little bit by forgoing stage 1 gcd.
I know you are working on the smallest double-checks (about 3 million
or so). Thus, it is not surprising you would be better off not running
the stage 1 GCD. First-time testers will be better off running the stage 1
GCD, and most double-checkers will be neutral to slightly better off.
The GCD cost grows at an N (log N)^2 rate. The stage 2 cost grows at
N log N (the cost of an FFT multiply) times something (the stage 2
bounds grow as N increases). I don't know if that something is
O(N) or worse. It doesn't matter. It does show that at
some point you are better off doing the stage 1 GCD for a 2%
chance of saving the cost of stage 2.
Regards,
George
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
