Toom testing, and unbalanced recursive calls in toom22.

Niels Möller nisse at
Tue Oct 20 14:26:45 CEST 2009

Torbjorn Granlund <tg at> writes:

> Do you agree that if that if we need toom22 to allow further unbalanced
> operands, we should not call mul_basecase for known-suboptimal operands,
> but instead call toom32 for these operands?


When I proposed to simply use mul_basecase, that was on the theory
than the difference between basecase and the best algorithm would
likely be very small over the range of practical interest. (And then I
don't care if basecase is highly sub-optimal for untypical sizes used
by the toom22 testcases).

A related question is, should we call toom22 for known-suboptimal
operands? We need to figure out where the border between toom22 and
toom32 is (and hopefully, also rule out use of e.g., toom42 for the
recursive call),


More information about the gmp-devel mailing list