>From: George Woltman <[EMAIL PROTECTED]>
>To: "David Campeau" <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]>
>Subject: Re: Mersenne: V20 beta #4 (will the beta never end?)
>Date: Thu, 20 Apr 2000 11:43:46 -0400
>
>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.
Given this, it does make sense to run it. Also, of course, there may be
some users who, while able to devote memory to stage II, have to cancel
scheduled defrags and so forth to do so; they may not mind losing an
average, say, half hour per exponent to do so.
>>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.
Also, of course, Brian's timings are based on only three found factors; this
sample may be too small to accurately estimate the chance of finding a
factor.
The smallest double-checks are being run by those who deliberately alter our
(I have three of my own waiting at the bottom of the list for my current QA
work to finish) connection times to claim them. Therefore, the casual users
who may not read all the documentation files will be better off doing the
stage 1 GCD.
>
>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.
And, if I follow you correctly, that point is well before most of the work
presently being done.
Regards,
Nathan Russell
______________________________________________________
Get Your Private, Free Email at http://www.hotmail.com
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
