Elementary functions. Algorithms and implementation.

Publication date 3 January 2006

algorithms computer arithmetic exponential least squares polynomial approximations logarithms rational approximations textbook trigonometric and logarithmic functions

Mathematics Subject Classification ID

Elementary functions (26A09) Software, source code, etc. for problems pertaining to special functions (33-04) Exponential and trigonometric functions (33B10) Numerical approximation and evaluation of special functions (33F05) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to numerical analysis (65-01) Computation of special functions and constants, construction of tables (65D20)

Review text

This book intends to help the specialist in designing hardware and software parts of floating-point systems and in investigating algorithms for computing elementary functions (exponential, trigonometric, roots, etc.) It also wants to introduce the nonspecialist to ideas and methods of these computations on computers and pocket calculators. Since the first publication of the book in 1997 (see Zbl 0892.65005), there have appeared new and improved techniques (bipartite table methods, formal proofs of floating-point algorithms, very accurate function libraries, etc.) to which the present new edition is drawing attention. An introductory chapter gives some notions central in computer arithmetic. This is followed by three parts of about seventy pages each. Part I concerns algorithms based on polynomial or rational approximations and, perhaps, tables, including the usual least squares polynomial approximations (Legendre, Chebyshev, etc.) and rational approximations, with a critical comparison of errors for specific functions (roots, tan, etc.) and for different representations of the same rational approximating functions, evaluated e.g., at \(5\cdot 10^5\) equally spaced values on \(0\leq x\leq 1\). This is followed by algorithms and architectures for evaluating polynomials, such as the E-method and Estrin's method, and by table-based methods of Tang, Gal, Wong, Goto, and others. The last chapter of this part is devoted to multiple-precision evaluation of functions, including applications of the AGM for various processors. Part II of the book deals with hardware-oriented algorithms that use additions and shifts only (``shift-and-add algorithms), simple and fast ones for exponential and logarithms, a detailed twenty-page discussion of the CORDIC algorithm and its variants (as implemented in the HP35 and many pocket calculators), and BKM iteration. Part III begins with three issues that are basic when accuracy is a major goal. The first of them is additive and multiplcative range reduction (algorithms by Cody and Waite, Payne and Hanek, Daumas et al.), particularly for trigonometric and logarithmic functions and roots, with a discussion of catastrophic inaccuracy due to poor reduction (numerically illustrated for \(\sin(10^{22})\)). The second issue considered is monotonicity, and the third is correct final rounding, the latter being discussed as a means for preserving symmetry and basic functional identities as well as for the portability of numeric software. The book also mentions table Maker's dilemma and situations of its nonoccurrence, furthermore, a probabilistic approach to final rounding, and Ziv's multilevel strategy. The final two chapters of Part III concern ``exceptional cases (underflow, overflow, ``inexact flags, etc., and a few remarks on the difficulties of \(x^y\)) and important examples of implementation, namely, the Cyrix FastMath Processor, the Itanium Processor and corresponding INTEL functions and the HP-UX compiler, etc. The rich content of ideas sketched or presented in some detail in this book is supplemented by a list of over three hundred references, most of them of 1980 or more recent. The book also contains some relevant typical programs.

Recommendations

Cited in

(44)

This page was built for publication: Elementary functions. Algorithms and implementation.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5715562)