Toom testing, and unbalanced recursive calls in toom22.

Niels Möller nisse at lysator.liu.se
Mon Oct 19 16:32:11 CEST 2009


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


More information about the gmp-devel mailing list