Muller J.-M. Elementary Functions. Algorithms and Implementation

Birkhauser, 1997. — 218 p.The elementary functions (sine, cosine, exponentials, logarithms.) are the most commonly used mathematical functions. Computing them quickly and accurately is a major goal in computer arithmetic. This book gives the theoretical background necessary to understand and/or build algorithms for computing these functions, presents algorithms (hardware-oriented as well as software-oriented), and discusses issues related to the accurate floating-point implementation of these functions. My purpose was not to give "cooking recipes" that allow to implement some given functions on some given floating-point systems, but to provide the reader with the knowledge that is necessary to build, or adapt algorithms to his or her computing environment.
When writing this book, I have had in mind two different audiences: specialists, who will have to design floating-point systems (hardware or software parts) or to do research on algorithms, and inquiring minds, who just want to know what kind of methods are used to compute the math functions in current computers or pocket calculators. Because of this, the book is intended to be helpful as well for postgraduate and advanced undergraduate students in computer science or applied mathematics as for professionals engaged in the design of algorithms, programs or circuits that implement floating-point arithmetic, or simply for engineers or scientists who want to improve their culture in that domain. Much of the book can be understood with only a basic grounding in computer science and mathematics: the basic notions on computer arithmetic that are necessary to understand are recalled in the first chapter.
A detailed presentation of the contents is given in the introduction. After a preliminary chapter that presents a few notions on computer arithmetic, the book is divided into three major parts. The first part consists of two chapters and is devoted to algorithms using polynomial or rational approximations of the elementary functions and, possibly, tables. The second part consists of three chapters, and deals with "shift-and-add" algorithms, i.e. hardware-oriented algorithms that use additions and shifts only. The last part consists of three chapters. It discusses issues that are important when accuracy is a major goal.
The previous books on the same topic (mainly Hart et al.'s book Computer Approximation and Cody and Waite's book Software Manual for the Elementary Functions) contained many coefficients of polynomial or rational approximations of the elementary functions. I have included relatively few such coefficients here, firstly to reduce the length of the book - since I also wanted to present the shift-and-add algorithms), and secondly because today it is very easy to obtain them using Maple or a similar system: my primarily concern is to explain how they can be computed and how they can be used. Moreover, the previous books on elementary functions essentially focused on software implementations and polynomial or rational approximations, whereas now these functions are frequently implemented (at least partially) in hardware, using different methods (table-based methods or shift-and-add algorithms, such as CORDIC): I have wanted to show a large spectrum of methods. Whereas some years ago a library providing elementary functions with one or two incorrect bits only was considered adequate, current systems must be much more accurate. The next step will be to provide exactly rounded functions (at least for some functions, in some domains), i.e., the returned result should always be the "machine number" that is closest to the exact result. This goal has already been reached by some implementations in single precision. I try to show that it can be reached in higher precisions.Computer Arithmetic
I Algorithms Based on Polynomial Approximation and/or Table Lookup
Polynomial Approximations
Table-Based Methods
II Shift-and-Add Algorithms
Shift-and-Add algorithms
The CORDIC Algorithm
Other Shift-and-Add Algorithms
III Range Reduction, Final Rounding and Exceptions
Range Reduction
Final Rounding
Miscellaneous