speed of unbalanced multiplication

Torbjorn Granlund tg at gmplib.org
Sat Jan 26 14:23:24 CET 2013

Zimmermann Paul <Paul.Zimmermann at loria.fr> writes:

  in GMP 5.1.0, a multiplication of n x m limbs for m < n can be slower than
  a multiplication of n x n limbs. Compare for example the line starting with
  775660 in the first output from speed, and the one starting with 1000000 in
  the second one below.

  This is quite embarrassing, especially when one optimizes an algorithm by
  reducing the multiplications sizes, and the algorithm gets slower...
I think "quite embarrassing" is an exaggeration for a 2% slowdown...

But sure, there is room for further improvement of the multiplication
code.  We have new code, see e.g. <http://gmplib.org:8000/gcd-nisse/>
which have the potential of smoothing things out.


More information about the gmp-devel mailing list