Architecture-Aware Classical Taylor Shift by 1

polynomial B(x) = A(x+1) from the coefficients of the polynomial
A(x). Taylor shift by 1 is the most time-consuming sub-algorithm of the
Descartes method for polynomial real root isolation.

Classical Taylor shift by 1 performs n(n+1)/2 integer additions where
n is the degree of A. Most existing implementations simply make calls
to an integer addition routine, often to the GNU-MP routine for exact
integer addition. This holds for the computer algebra system Maple, for
Hanrot's implementation of the Descartes method, and for von zur Gathen
and Gerhard's implementation of the Taylor shift by 1. By contrast, the
saclib library of computer algebra programs uses a specialized routine
that does not make any function calls.

Our method is further specialized to take advantage of current processor
architectures. The method uses instruction-level parallelism and avoids
pipeline stalls; it also makes efficient use of the memory hierarchy.
Unlike the GMP-package, our implementation does not use assembly
language. The run-time efficiency of our method depends on several
parameters that can be automatically tuned to the underlying system.

We use performance counter measurements to count processor cycles,
instructions, and cache hits and misses. Our overarching goal is to
determine the input size for which asymptotically fast methods
outperform classical methods.