unbalanced multiplication and division
Paul.Zimmermann at loria.fr
Thu Oct 29 20:45:40 CET 2009
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.
* 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.
It would be interesting to see how those curves look like with the current
PS: you might also have a look at slides 108 and 110.
More information about the gmp-devel