Toom-4.5 (aka Toom-5x4, Toom-6x3, Toom-7x2)
Niels Möller
nisse at lysator.liu.se
Tue Oct 13 10:00:50 CEST 2009
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
More information about the gmp-devel
mailing list