Toom testing, and unbalanced recursive calls in toom22.

Paul Zimmermann Paul.Zimmermann at
Mon Oct 19 16:46:17 CEST 2009


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

yes that's the idea.

> 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'm very curious to see a real comparison of both variants.


More information about the gmp-devel mailing list