Hi,
At 04:07 PM 11/6/99 EST, [EMAIL PROTECTED] wrote:
>Was your code doing a true Fermat-mod DWT, or were you attempting to
>factor instead the Mersenne number M(2^25-1) = (2^(2^24)-1)*(2^(2^24)+1)?
Prime95 uses a true Fermat-mod DWT.
>Impressive - can you give us a brief summary of the most time-impacting
>changes you made, and were these to the C source or in ASM?
There were a few things in giants that were not done efficiently.
For example, dividing one huge number by another was done using
reciprocals and then multiplying. Well, 99.9% of the time in a GCD
the quotient will be less than 2^32 and can be derived by one floating
point divide on just the high order bits. It was also a bit of a
memory hog.
I also upgraded giants from 16-bit to 32-bit, made use of some
ASM helper routines, cleaned up memory management, etc.
The changes I've made have been forwarded to Dr. Crandall for
possible incorporation into a future release of giants.
>>BTW, I know of no other publicly available implemetation of the fast GCD.
>>It was written by J. P. Buhler.
>
>I know little about it, except that Crandall mentioned it took them
>the better part of 6 months to get the thing written and debugged.
>Better them than you, right? :)
Absolutely! And it is quite elegant. You should be able to incorporate
it into your code with little trouble. I had little trouble upgrading
it to do modular inverses too.
Regards,
George
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
