speed of unbalanced multiplication
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