toom54

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> Yes, Toom-4.5 inversion is structured with the Toom'n'half strategy. It
> shouldn't be difficult to write a single function working both as 54 and
> 63 :-)

That's a question of taste. I'd prefer separate functions, and then
leave choice of stratey to mpn_mul. But which style really makes the
most sense depends a bit on where relevant thresholds end up.

toom54 is really a small and simply function now, the interesting piece
is just 35 lines. The reason toom63 is a bit larger is that evaluation
of the degree 2 polynomial (3 coefficients) is inlined.

One could save some code size by writing some helper functions for this
case as well (shared by toom[3456]3 and possibly also toom32). Or if the
function call overhead is too expensive for toom33 and toom32,
mpn_toom_eval_dgr2_pm1 could be done as a macro rather than a function,
even if that would just reduce source code size, not object code size.

> Yes, things have changed, the main such change comes from the new toom6h
> and toom8h functions. It would be nice to regenerate the diagrams with the
> new algorithms. I guess toom72 will not cover a wide region in a current
> version.

I think it might provide some insight to do benchmarks along fixed
ratios. For each algorithm, there's a supported range. Take both end
points and the midpoint. Along each of these three lines, benchmark for
a range of sizes with a fixed ration, and see where the algorithm beats
other algorithms which support the same ratio. There's some complication
from the unbalanced calls (which one would want to use an optimal
algorithm choice), but I hope that will have a fairly small influence on
the results.

It would also be interesting to prepare some graph showing for each
function which functions it may use for the recursive calls (with a
close-to-optimal algorithm choice). E.g., I suspect toom32 shouldn't
call anything but basecase, toom32 and toom22.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.