Implementation of subquadratic GCD?
Josh Liu
zliu2 at student.gsu.edu
Thu Dec 2 23:23:35 CET 2004
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
More information about the gmp-discuss
mailing list