GMP 4.3 multiplication performance

[Niels Möller]

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).

/Niels