New mpn_divexact code
Paul.Zimmermann at loria.fr
Thu Aug 3 18:29:56 CEST 2006
> Just to make it clear, does you precomputation FFT library help
> if I am multiplying, say, a 1e9 digit operand with several
> different 1e8 digit operands? Does it then help to pre-transform
> the 1e9 digit operand?
Yes it helps. The transform length will be 1e9+1e8. You'll save one transform
for each multiply, starting from the 2nd.
> I yesternight implemented what you suggested back in 2003, or at
> least I think it is what I have implemented, though there are
> some apparent discrepances.
I'll look at that tomorrow.
> As written, the new code cannot use the mul_lo code from GMP-ECM,
> since that apparently needs extra space at the destination, not
> just the n requested low limbs. The present GMP 4.2 mullow_n is
> probably slower than the GMP-ECM code, but it fits better here.
> I'll look into this soon.
For a recursive usage, having 2n allocated limbs for mul_lo is very nice,
since you can use either mpn_mul or mul_lo at any place.
More information about the gmp-devel