Toom testing, and unbalanced recursive calls in toom22.

[Torbjorn Granlund]

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

  Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:
  
  >> Say mpn_toom22_mul is called with inputs of size an = 178, bn = 89.
  >
  > I guess you mean an = 178, bn = 118 from the numbers below.
  
  Ooops, yes that's what I mean.
  
  > another solution is to (pseudo-)multiply b by B^30, then b0 and b1 have both
  > 59 significant limbs. See Section 1.3.5 of [1]. This will keep the unbalanced
  > ratio between a and b for a0*b0 and a1*b1.
  
  So instead of two balanced and one (possibly very) unbalanced
  recursive call, you get one balanced call and two unbalanced ones,
  with the same ratio as the inputs. It's not at all clear to me which
  variant is most efficient (if the recursive calls use schoolbok,
  there's no difference, but for subquadratic recursive multiplications,
  I have no idea).
  
I think two less unbalanced calls are worse thatn one more unbalanced
calls.  In particular when the more unbalanced calls falls into
mul_basecase.
  

-- 
Torbjörn