Toom-4.5 (aka Toom-5x4, Toom-6x3, Toom-7x2)

[Torbjorn Granlund]

Torbjorn Granlund <tg at gmplib.org> writes:

  There are new diagrams at gmplib.org/devel/ now, with the new toom code
  and with an attempt at the suggested colour scheme.
  
  The new functions are all some shade of blue.  And yes, there is a lot
  of blue!  :-)
  
  (The Pentium4 diagrams are not updated, nor are the larger-scale
  diagrams that should be available by clicking the smaller diagrams.)

There are now more comprehensive diagrams.

I use green for 5 eval points, pink-violett for 6 eval points, red for 7
eval points, and blue for 8 eval points.  Karatsuba also uses a shade of
pink, since it is not close to the 6 point algorithms; the 4 point
toom32 uses grey.  FFT use yellow/brown (FFT ng is not used by the
measurement functions).

There are entire regions where we get around 1.5 speedup with the new
set of toom functions.

The only operands that does not get speedup compared to the present gmp
repo are balanced operands and operands where the smaller operand <
MUL_TOOM22_THRESHOLD.  The former could be improved with toom55, toom66,
toom77, etc, the latter could be improved with toom32 accepting
transformed operands.

Where will this madness stop?  Would a toom_50_50 have a place?
Clearly, we cannot add 100 toom function as C code.  If we need 100
different toom functions, we need to describe the evaluation and
interpolation steps as some sort of byte code.

I wonder if some special DFT-based multiplication could compete with
this toom foolery, to put a lower cap on # of eval points.  It does not
necessarily need to use the FFT algorithm.

-- 
Torbjörn