New mpn_divexact code

[Paul Zimmermann]

> 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.

Paul