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

Second Edition. — Birkhauser, 2006. — 274 p.Since the publication of the first edition of this book, many authors have introduced new techniques or improved existing ones. Examples are the bipartite table method, originally suggested by DasSarma and Matula in a seminal paper that led Schulte and Stine, and De Dinechin and Tisserand to design interesting improvements, the work on formal proofs of floating-point algorithms by (among others) John Harrison, David Russinoff, Laurent Th.ery, Marc Daumas and Sylvie Boldo, the design of very accurate elementary function libraries by people such as Peter Markstein, Shane Story, PeterTang, David Defour and Florent de Dinechin, and the recently obtained results on the table maker’s dilemma by Vincent Lef`evre. I therefore decided to present these new results in a new edition. Also, several colleagues and readers told me that a chapter devoted to multiple-precision arithmetic was missing in the previous edition. Chapter 5 now deals with that topic.
Computer arithmetic is changing rapidly. While I am writing these lines, the IEEE-754 Standard for Floating Point Arithmetic is being revised.1 Various technological evolutions have a deep impact on determining which algorithms are interesting and which are not. The complexity of the architecture of recent processors must be taken into account if we wish to design high-quality function software: we cannot ignore the notions of pipelining, memory cache and branch prediction and still write efficient software. Also, the possible availability of a fused multiply-accumulate instruction is an important parameter to consider when choosing an elementary function algorithm.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.Some Basic Things About Computer Arithmetic
I Algorithms Based on Polynomial Approximation and/or Table Lookup
Polynomial or Rational Approximations
Table-Based Methods
Multiple-Precision Evaluation of Functions
II Shift-and-Add Algorithms
Introduction to Shift-and-Add Algorithms
The CORDIC Algorithm
Some Other Shift-and-Add Algorithms
III Range Reduction, Final Rounding and Exceptions
Range Reduction
Final Rounding
Miscellaneous
Examples of Implementation