unbalanced multiplication and division
Torbjorn Granlund
tg at gmplib.org
Thu Oct 29 21:05:58 CET 2009
Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:
on http://www.loria.fr/~zimmerma/talks/mca_raim09.pdf, slide 25, I have
produced a graph of the multiplication i x (n-i) limbs and of the division
n / i limbs (GMP 4.3.1 on a Pentium M). If you consider that the division
n / i is really a multiplication i x (n-i) with the (n-i) quotient computed
on the fly, we should have similar timings. However:
* the division is about 2 times slower than the multiplication. This can be
partly explained by the fact that the "recursive division" costs 2M(n) in
the Karatsuba range.
We had much new division at the mpn level in GMP 4.3, but it was not
enabled at the mpz level. It is now partially enabled, but the new
faster quotient-only functions have not been enabled.
I expect this to be addressed fairly soon.
* more strange, the graphs for multiplication and division are non monotonic.
The multiplication cost increases until i=2500, then slightly decreases and
increases again until i=5000. The division costs increases until about
3500, then decreases.
I would say that "in theory", both curves should be non-decreasing, since the
total work i x (n-i) increases with i.
You should know that our focus have become 64-bit machines since GMP
4.3. That does not mean we do not optimise for 32-bit machines,
only that they might get less attention.
You might want to re-measure after having replaced the used gmp-mparam.h
with a newly generated one. The right location for the new file is
mentioned in the tuneup output.
But even when well-tuned, the code for unbalanced multiplication in GMP
4.3 leaves something to be desired. If you have followed the discussion
at gmp-devel, you know that we're working on a solution.
It would be interesting to see how those curves look like with the current
unbalanced code.
No new code has been committed.
--
Torbjörn
More information about the gmp-devel
mailing list