Toom testing, and unbalanced recursive calls in toom22.

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  When I proposed to simply use mul_basecase, that was on the theory
  than the difference between basecase and the best algorithm would
  likely be very small over the range of practical interest. (And then I
  don't care if basecase is highly sub-optimal for untypical sizes used
  by the toom22 testcases).
  
I see.  Perhaps that is indeed true.

  A related question is, should we call toom22 for known-suboptimal
  operands?

No...it is nice that you begin to understand the GMP philosophy.  :-)

But when choosing algorithm, we will probably need to do some
simplifying compromises.  For many areas, the difference of the best and
2nd best algorithms will be close to zero.  If we can identify those,
and thereby make the shapes easier to manage, then we should do that.

  We need to figure out where the border between toom22 and
  toom32 is (and hopefully, also rule out use of e.g., toom42 for the
  recursive call),

Yes.

My measurement program (the graph-generating one) completely botched the
point at oo.  The program built a complete table of sizes and best
algorithm + speed (plus 2nd best, plus current mul.c speed), which could
have been used for the multiplication for the oo point.  Alas, that
would have required modification of each toom function, to make them
look in my table.

-- 
Torbjörn