Hi,
At 07:55 PM 10/28/99 EDT, [EMAIL PROTECTED] wrote:
>Jason Papadopoulos wrote:
>
>> Except that every once in a while you'd have to perform a GCD, and
>> a GCD on million-digit size numbers takes about a day (no kidding!
>> There seems to be no fast way to do one!)
>
>A day seems somewhat of an overestimate (though maybe it takes that
>long on a Pentium - I don't know.) On a decently fast Alpha, say a 500MHz
>21164, I can do a million-digit (and note I mean base-10 digits, not bits)
>GCD in under 5 minutes
When I was making a P-1 attempt on F24 I reported the GCD on my PII-400
was taking a day.
Since F24 is 5 million digits your computer would take 5 minutes * 5^2,
or 2 hours. Given your machine is faster, my code is 32-bit, my code
does an extended GCD, the Alpha is a better architecture, and your code
is probably better - you come up with the factor of 12 difference.
Now the good news. Crandall's giants code has an implementation of
the O (n * log n * log n) GCD in it. It was painfully slow. After two
days of optimizing, I will be able to do that 5 million digit
GCD in an estimated 30 minutes.
BTW, I know of no other publicly available implemetation of the fast GCD.
It was written by J. P. Buhler.
Regards,
George
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
