GMP 4.3 multiplication performance
nisse at lysator.liu.se
Thu Jun 4 13:49:54 CEST 2009
Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:
> if we extend your argument, it would also to have functions to evaluate
> at quadruples of points, say 2, -2, 1/2, -1/2. In particular for even-degree
> polynomials, the middle coefficients can be shared between 2 and 1/2.
Hmm. Say we have degree 2, to make things simple. Then you want to compute
f(2) = a_0 + 2 a_1 + 4 a_2
f(-2) = a_0 - 2 a_1 + 4 a_2
4 f(1/2) = 4 a_0 + 2 a_1 + a_2
4 f(-1/2) = 4 a_0 - 2 a_1 + a_2
So one can save one multiplication by 2 in 2 a_1 of we compute all
four values together, instead of doing them two at a time.
(Pragmatically, one might solve this by having the helper function
take the middle argument preshifted, so the caller can do that
operation and keep the result).
And we also have a different symmetry, in that a function to compute
f(±2) can also be used to compute f(±1/2) if we pass coefficients in
reverse order (and somehow deal with the fact that in general a_2 is
of smaller size than the other two coefficients).
More information about the gmp-devel