Implementation of subquadratic GCD?

[Josh Liu]

I believe that the best place to find a subquadratic GCD is from Niels  
Moller's archive: http://www.lysator.liu.se/~nisse/misc/ . Also, check  
out my project for  
centrinia/design/base/N/medium/arithmetic/gcd/Euclid/Schonhage/ . Both  
use GMP as their interface. In response to Alex's post, I believe that  
Crandall's library is not free.

I would truly appreciate it if you can look at my project's version. It  
is rather slow as it does not use Lehmer's trick in the basecase, but  
if you can decipher it, it should be useful as well. Even I would use  
Moller's implementation, but if you have the chance, you can probably  
hack my implementation more easily, if you avoid the 900 line recursive  
function.

Also, I would be lead to believe that no one knows if there are any  
interpolation matrices for 4-Way Toom-Cook multiplication that are  
superior to what I posted on the two GMP mailing lists. This is my  
third attempt to get attention to this subject, so please, if anyone  
has any knowledge regarding this matter, please respond. Thank you.

Also, I have spent some time creating a multiplication algorithm for  
polynomials with coefficients in a field with characteristic 2. I have  
also implemented a Schoenhage-Strassen integer multiplication  
algorithm. Both of these algorithms involve a final interpolation to  
find the true coefficients of the polynomial or the digits of the  
integer. This final interpolation is faster than using one more step of  
the fast Fourier transform. The integer multiplication method has been  
shown to be, at best, 50% faster than the GMP multiplication function  
system. The funny thing is, the most time consuming portion of the  
multiplication is the bitwise complement of a vector of limbs. I would  
appreciate it if anyone can give me more pointers as to what to do to  
speed up the complement. I also have a Nussbaumer polynomial  
multiplication routine that works for polynomials with coefficients in  
GF(2).

Josh Liu's GnuPG public key is available at <a  
href="http://www.student.gsu.edu/~zliu2/centrinia.html">http:// 
www.student.gsu.edu/~zliu2/centrinia.html</a>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20041202/a9509ca7/PGP.bin