unbalanced multiplication and division

[Paul Zimmermann]

       Hi,

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

Paul

PS: you might also have a look at slides 108 and 110.