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.
[snip]
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.
--
Torbjörn
More information about the gmp-devel
mailing list