Efficient implementation of polynomial multiplication
Décio Luiz Gazzoni Filho
decio at decpp.net
Fri Mar 5 13:12:56 CET 2004
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Hello,
I'm working on a project using GMP, and I'm stuck trying to make a fast
routine for multiplying polynomials (with coefficients from Z/pZ, i.e. the
size of the coefficients is bounded.) The technique I'm used is called
`binary segmentation' and consists of evaluating the polynomials f(x), g(x)
at x = 2^b, with b > p^2*max(deg(f),deg(g)) so that there's no risk of carry
from one polynomial coefficient to the other. So here's how the resulting
integers f(2^n) = a0 + a1*2^n + a2*2^(2n) + ... and g(2^n) = b0 = b1*2^n +
b2*2^(2n) + ... look like (sorry for the ASCII art):
0 n 2n
a0 00...00 a1 00...00 a2 00...00 ...
b0 zero-pad b1 zero-pad b2 zero-pad ...
So my question, what is the most efficient way of building this integer (and
later removing coefficients from it at the same 0,n,2n,... boundaries), while
still being portable? Of course I could use lshifts and adds to insert the
coefficients, and mpz_fdiv_r_2exp and rshifts to remove them, but this is
hopelessly slow: my routine spends the bulk of its time doing the shifts.
I'm thinking either something that manipulates the mpz_t->_mp_d array
directly, or something using mpz_import/mpz_export... anyway, I hope someone
on the list can help me with this.
I was going to put my current code here, but as it stands it's not generating
meaningful results.
Thanks for the help
Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)
iD8DBQFASKcPFXvAfvngkOIRAlh6AJ9cPhPv8l8ie9F0Gtn8vJTpHrW08wCgg6Yd
gsFW4mz0DZYPiV42Zo1yp2E=
=+UnQ
-----END PGP SIGNATURE-----
More information about the gmp-discuss
mailing list