GMP 4.3 multiplication performance

Torbjorn Granlund tg at
Thu Jun 4 11:51:46 CEST 2009

I looked at the object size of the toom functions.  They are larger than
I expected, meaning that reducing their sizes might be performance

The file sizes vary from around 1000 bytes to around 4500 bytes.  The
smallest file is toom3_sqr.o on most machines, toom2_sqr.o on other
machines.  The largest file is toom62_mul.o.

I don't think saving object file size should be the most important goal
for GMP.  Performance should be the primary goal.  Only to the extent
object file size affects performance, we need to worry about it.

Don't get me wrong, we should keep GMP lean, and we should not bloat it
for little performance gain.

We have to be careful if we write evaluate functions for toom, to make
sure we add overhead only propotional to the operand sizes.  That means
some cycles to toom44 matter very little, while adding cycles to toom22
or toom32 or toom42 should be avoided.

For toomNN, the symmetric cases, we should have a single function for
evaluation, used for both operands of toom44_mul, and for the single
operand of toom4_sqr?


More information about the gmp-devel mailing list