Computer-Hardware Evaluation of Mathematical Functions

The following sections are included:

• Dedication
• Preface
• Acknowledgments
• Contents

The first section of this chapter is on errors. In general, for a given function we seek a good hardware-implementable approximation that, ideally, will be computable with only simple operations: table lookup, addition, and multiplication. Evidently, this will involve some errors—from both the mathematical nature of the approximation and various machine limitations—and we shall consider how to derive bounds on such errors. The general manner in which such bounds are obtained in the book is such that in some cases they may be considered crude, in so far as the magnitudes are “worst-case”, slight overestimates. (In particular instances, tighter bounds can be obtained in a straightforward manner, although the tedium involved might be substantial.) But they are nevertheless useful as a measure of confidence and as guides to implementation parameters. And they will certainly suffice for the writing of good poetry…

This chapter is primarily on algorithms for high-speed multiplication and division; it is intended to be an introduction or a review, depending on the reader's background. All such algorithms, as well as those for many of the functions we are interested in, are based on redundant number-representation systems, i.e. systems in which a given number has more than one representation. Therefore, an introduction to these systems precedes the two main sections that make up most of the chapter. Some of the discussions on the evaluation of other functions (in Chapters 5 and 8) rely on similarities with division algorithms, and frequent references are made there to particular points in this chapter. So even the reader who has a good knowledge of basic computer arithmetic should at least skim through the chapter. (Additional explanation is given in the remainder of this introduction.) This is not a book on basic arithmetic operations, so there is a great deal that we have left out. The reader who requires additional information should consult standard books on computer arithmetic [1-4]…

The CORDIC algorithms have long been studied for the evaluation of elementary functions. Their origins lie in a special-purpose computer, the Coordinate Rotational Digital Computer, that was designed for the evaluation of some trigonometric functions [1, 2]. Subsequently, the algorithms were extended to other elementary functions [3, 4], and new variants continue to appear [5]. As implied by the name, the underlying idea is that of a rotation in a geometric space. The CORDIC algorithms can also be derived through the concept of normalization, a more “algebraic” process that is discussed in Chapter 5…

This chapter covers extensions of the CORDIC algorithms of Chapter 3. The main basis of the variants discussed here is the use of redundant number representations to achieve high performance—by allowing the elimination of arithmetic operations in some cyles, facilitating faster arithmetic, and making it easy to use radices larger than two…

The concept of normalization was briey introduced in Section 2.3 and several such algorithms given there for division. For the reader who has arrived here directly, or who simply needs a reminder, the “definition” is repeated just below. Nevertheless, such a reader should note that some aspects of the material covered in Chapter 2 are very relevant here (and in Chapter 8), and it is helpful to be familiar with the redundant number representations of Section 2.1 and the division algorithms of Section 2.3…

Polynomial approximations are good for computer function approximations, in so far as they can be evaluated with reasonable efficiency. A polynomial of a given degree can be evaluated using a fixed number of additions and multiplications, and there exist algorithms that will keep the number optimally low. Nevertheless, on their own, or if used without sufficient care, they might be not particularly well suited to hardware implementation: in some cases—depending on the function, or the argument, or both—obtaining high accuracy will require a large number of terms and, hence, time-consuming operations. For hardware evaluation, the best uses of polynomials are in combinations of low-degree polynomials and lookup tables; that is the subject of Chapter 7. In this chapter we shall discuss polynomials in some generality, making few assumptions of the reader's background, or of what the reader might consider “low degree”, or of what hardware functional units one might have in mind and how this might influence the choice of evaluation method…

A computer can represent only a finite number of the real numbers. So, in principle, the simplest method for the evaluation of a function, f, at an argument, x, is to use a table that is addressed with values of x and whose outputs are the corresponding values of f(x). This also ought to be fast, as the single step involves no arithmetic computations. In practice, however, this simple method is of limited worth. If there are m possible values of x, then a table of 2^m elements is required, which is impractical, except for small values of m. So in practice the essential idea is typically combined with some other technique that involves some arithmetic operations. One way to do so is to partition the bits of x into groups, use the groupings to access tables that contain some partial information on f(x), and then, with some arithmetic operations, combine the outputs of these tables to obtain the full f(x). We thus have a whole range of methods that involve the use of a variety of tables and arithmetic operations, with the latter ranging from one or two additions to more complex polynomial evaluation…

The first section of this chapter is a short one on the use of polynomials to compute all three functions; we have separated this from the other two sections because of the “unified approach” of the particular work on which the section is based [9]. The second section covers the computation of reciprocals. And the third covers the computation of square roots and their inverses; square roots are especially important given their place in the IEEE standard on oating-point arithmetic. Most of the algorithms discussed in the latter two sections are based on one or another form of normalization. Other algorithms can be obtained directly or indirectly on the basis of the discussions of Chapters 6 and 7; for example, the bipartite-table method (Section 7.1) was invented specifically for reciprocals [1]…

The following sections are included:

• References
• Index