squaring vs multiply

Torbjorn Granlund tg at gmplib.org
Fri Nov 8 20:53:11 CET 2013

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

  Moreover GMP is using Schönhage-Strassen's algorithms, where the pointwise
  multiplications are not negligible, thus we should have a ratio well above 2/3.
  However in GMP 5.1.3 the ratio is around 2/3, and sometimes even below:
  Any explanation?
I can speculate, at least.

A significant fraction of the point-wise products' time will be spent in
mpn_mul_basecase/mpn_sqr_basecase.  The time ration for those is close
to 1/2.  This ratio seems to be reflected in toom functions.

It is also possible that cache effects play a part; squaring will have
slightly better spatial and temporal locality.


More information about the gmp-devel mailing list