At 09:10 AM 6/8/99 +0100, you wrote:
>On Mon, Jun 07, 1999 at 04:37:32PM -0500, JON STRAYER wrote:
>> > You need to test exponent (10000000 / log 2) = 33219281 or above.
>
>Time for an n bit multiply using DWT is O(n log n) plus some fiddly
>bits to do with decreasing precision available when using longer
>convolutions - I'd probably estimate this as O(log log n). As it
>takes n iterations for each test then to test an n digit number using
>the Lucas Lehmer test with DWT takes O(n^2 . log n . log log n).
>
>If we say that the current exponent is about 6.5 million then we need
>to test one which is approx 5 times bigger. Using the above formula I
>make this 29.97 times longer for a 5 times increase in exponent size
>starting at 6.5 million.
My PII-400 is showing 1.121 and 1.236 seconds per iteration for FFT sizes
of 1.75M and 2M. The crossover point will be somewhere in the vicinity
of 35,000,000. Thus, the smallest 10 million digit Mersenne number
will take 33219281 * 1.121 seconds or 431 days. In a few years when 2 GHz
chips are readily available this will be a more reasonable 80 days.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
