Toom testing, and unbalanced recursive calls in toom22.

[Niels Möller]

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).

Regards,
/Niels