Toom-4.5 (aka Toom-5x4, Toom-6x3, Toom-7x2)

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> Evaluation in 3 could make use of mpn_addlsh1 for multiplying by 3.  It
> is faster on some machines and slower on some machines than mpn_lshift.

Then evaluation in 3 (full list of points: 0, oo, ±1, ±2, ±3) might
actually be faster. Since the resulting division by 15 can be done
with bdiv_dbm1c for both 64 and 32 bit limb sizes.

Selection of the best points seems tricky, on the border to black
magic ;-)

I've previously said that I think quadruples like ±2 and ±1/2 or ±x
and ±1/x are good, but now I'm not sure why I said that. It seems the
symmetry +x, -x can be exploited in interpolation (after initial
butterflies, we get a matrix with a regular structure, which makes
early recombination possible. Is there any use of the other symmetry,
x, 1/x, in the interpolation? I don't see that.

At the moment, the only advantage I see to using x and 1/x is that
they could share a single evaluation function (if we somehow handle
the problem that one of the coefficients may be of less than full
size). 

Regards,
/Niels