Overview

Our objective in this chapter is to find efficient algorithms for evaluating dementary functions (like e ^x , In x, sin x, cos x, etc.) in hardware. These algorithms should be accurate and sufficiently fast in comparison to alternative algorithms implemented in software. Such algorithms are especially useful when designing scientific hand-held calculators and numerical (usually floating-point) processors ([12]).

One straightforward method is the use of a look-up table. To evaluate y=F(x) where x and y are numbers of length n bits, a ROM of size 2 ⁿ n is required. For n ?20, this size is prohibitive ( ?16M). Another method is to use a Taylor series expansion; e.g.,

This series converges rapidly for a fractional argument x. However, for x close to 1, a large number of steps is needed. In addition, its hardware implementation is complex, since separate logical networks are needed for different elementary functions. Even for software implementations there exist more efficient algorithms requiring a smaller number of computational steps for the same precision. The most commonly used are based on either polynomial or rational approximations.

Consider, for example, the exponential function e ^x. We can express it in the form and partition the exponent x log ₂ e into its integer part I and its fractional part f, i.e., xlog ₂ e=I+ f. Thus,

The incorporation of the factor 2 ^I