unbalanced multiplication and division

[Torbjorn Granlund]

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