On Mon, Jun 07, 1999 at 04:37:32PM -0500, JON STRAYER wrote:
> I'm I correct in thinking that since the exponent is five times the
> size of current exponents that the LL test will take 25 times as
> long (give the same processor)?
>
> > 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.
Probably ;-)
--
Nick Craig-Wood
[EMAIL PROTECTED]
http://www.axis.demon.co.uk/
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
