Toom testing, and unbalanced recursive calls in toom22.

[Torbjorn Granlund]

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

  Some possible solutions:
  
  1. Have TOOM22_MUL_MN_REC always use basecase for too unbalanced
     products (and trust that in practice toom22 will not be called for
     sizes where this is a poor choice). Also, for size 2n x n+1, the
     most unbalanced case mpn_toom22_mul can handle, that function is
     probably not the best choice.
  
  2. Have TOOM22_MUL_MN_REC choose between toom22, toom32 and basecase,
     using some conditions.
  
  3. Let TOOM22_MUL_MN_REC use the general mpn_mul function for
     unbalanced multiplication. This has implications on the use of
     scratch space (as long as mpn_mul doesn't use an itch/scratch
     interface, scratch allocated for toom22 will be wasted. And if
     mpn_mul is eventually itchified, this gives a rather unpleasant
     circular dependency.
  
  I think all the other toom functions call mpn_mul for the unbalanced
  recursive product, but that overhead is more noticeable for toom22, I
  guess.
  
  What's reasonable to do?
  
I don't think toom22 should call mul.c for the point-at-oo evaluation.
The overhead is simply too large for these small operands.

I also don't think (1) is good.

(2) is my favourite.

But except when tuning (as told by TUNE_PROGRAM_BUILD) we can often
exclude various alternatives.  For example, if

  MUL_TOOM33_THRESHOLD / MUL_TOOM22_THRESHOLD < 2

we know that toom22 will always call mpn_mul_basecase.

But we may also keep the code like it is, and simply forbid the operands
that lead to too unbalanced recursive calls.  That's my approach in the
measurement program generating the graphs at gmplib.org/devel/.

This isn't too hard to find out in closed form, I suppose.  I was lazy
in the measurement program, and wrote a recursive predicate.  It should
be a simple function of MUL_TOOM22_THRESHOLD and (un-vn).

-- 
Torbjörn