The Descartes method for polynomial real root isolation can be performed with respect to monomial bases and with respect to Bernstein bases. The first variant uses Taylor shift by 1 as its main subalgorithm, the second uses de Casteljau's algorithm. When applied to integer polynomials, the two variants have co-dominant, almost tight computing time bounds. Implementations of either variant can obtain speed-ups over previous state-of-the-art implementations by more than an order of magnitude if they use features of the processor architecture. We present an implementation of the Bernstein-bases variant of the Descartes method that automatically generates architecture-aware high-level code and leaves further optimizations to the compiler. We compare the performance of our implementation, algorithmically tuned implementations of the monomial and Bernstein variants, and architecture-unaware implementations of both variants on four different processor architectures and for three classes of input polynomials.

We present algorithms that outperform straightforward implementations of classical Taylor shift by 1. For input poly-nomials of low degrees a method of the SACLIB library is faster than straightforward implementations by a factor of at least 2; for higher degrees we develop a method that is faster than straightforward implementations by a factor of up to 7. Our Taylor shift algorithm requires more word additions than straightforward methods but it reduces the number of cycles per word addition by reducing memory traffic and the number of carry computations. The introduction of signed digits, suspended normalization, radix reduction, and delayed carry propagation enables our algorithm to take advantage of the technique of register tiling which is commonly used by optimizing compilers. While our algorithm is written in a high-level language, it depends on several parameters that can be tuned to the underlying architecture.

This work discusses an FPGA implementation study of the Bene Permutation Network (BPN). The BPN, originally developed for connecting devices in telephone switching, is a circuit of size O(n log n) and O(log n) depth, built from 2 x 2 switches, which is capable of performing an arbitrary permutation. The BPN provides an asymptotic improvement in area over the straightforward network built with multiplexers, and the work presented here shows that an FPGA implementation uses less area for networks as small as size 4. The implementation presented in this paper uses a special-purpose tool to synthesize and place and route the circuit. The place and route tool can be used to systematically explore alternative place and route strategies and was used to obtain significantly better area utilization and timing performance compared to general-purpose tools. In addition, several general improvements and extensions were discovered that further improve performance and reduce area.