Elementary Functions:: Algorithms and Implementation [Hardcover]

Jean-Michel Muller (Author)

Book Description

ISBN-10: 081763990X | ISBN-13: 978-0817639907 | Publication Date: July 15, 1997 | Edition: 1

This book gives the concepts and background necessary to understand and build algorithms for computing elementary functions, presenting and structuring the algorithms (hardware- oriented as well as software-oriented), and discusses issues related to the accurate floating-point implementation. The purpose is not to give "cookbook recipes" that allow one to implement some given function, but to provide the reader with the knowledge that is necessary to build, or adapt, algorithms to their specific computing environment. Topics and Features: * background material reviewed in Chapter 2, Computer Arithmetic * polynomial and  rational approximations * table based methods * shift-and-add algorithms thoroughly covered in Part Two * CORDIC algorithm * range reduction and accuracy covered in Part Three * Web site for the book containing additional resources and selected code The book provides an up-to-date presentation of the information needed to understand and accurately use mathematical functions and algorithms in computational work and design. Graduates, professionals and researchers in scientific computing, software engineering, and computer engineering will find the book a useful reference and resource.

Editorial Reviews

Review

"There a few classic books on algorithms for computing elementary functions.... These books focused on software implementation using polynomial approximations. Perhaps Muller's book is destined to become a new classic in this subject, but only time will tell.... Muller's book contains few theorems and even fewer proofs. It does contain many numerical examples, complete with Maple code.... In summary, this book seems like an essential reference for the experts (which I'm not). More importantly, this is an interesting book for the curious (which I am). In this case, you'll probably learn many interesting things from this book. If you teach numerical analysis or approximation theory, then this book will give you some good examples to discuss in class."   —MAA Reviews (Review of Second Edition) "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."   —Zentralblatt MATH (Review of Second Edition) "This book is devoted to the computation of elementary functions (such as sine, cosine, tan, exponentials and logarithms) and it is intended for specialists and inquiring minds as the author says in his preface. I also think that the book will be very valuable to students both in numerical analysis and in computer science.  The author is well known among people working on computer arithmetic. I found the book well written and containing much interesting material, most of the time disseminated in specialized papers published in specialized journals difficult to find. Moreover, there are very few books on these topics and they are not recent."   —Numerical Algorithms (Review of First Edition) "This book is intended for two different audiences: specialists, who have to design floating-point systems…or to do research on algorithms, and inquiring minds, who just want to know what kind of methods are used to compute mathematical functions in current computers or pocket calculators. Because of this, it will be helpful for postgraduate and advanced undergraduate students in computer science or applied mathematics as well 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."   —Mathematica Bohemia (Review of First Edition) "The author presents a state-of-the-art review of techniques used to compute the values of common elementary functions. Chapter 1 introduces the goals of techniques that produce good approximations. Chapter 2 reviews topics in computer arithmetic, including number representation (redundant and nonredundant) and the IEEE standard for binary floating-point arithmetic. Chapters 3 and 4 review the techniques (polynomial, rational, and table-based) used in some current microprocessors. Chapters 5, 6, and 7 review shift-and-add techniques, including the CORDIC method frequently used by calculator designers. Chapter 8 discusses range reduction. Chapter 9 discusses techniques that help produce correctly rounded results."   —Mathematical Reviews (Review of First Edition) "A must for those involved with designing numerical processors or mathematical software, the book should also interest calculus students for the new perspectives it offers on topics they might think they know very well. Suitable for upper-division undergraduates through faculty."   —Choice (Review of First Edition) "This fascinating book describes the techniques used by high-level compilers and by pocket book calculators to generate values of the common elementary mathematical functions."   —ASLIB Book Guide (Review of First Edition) "The author fully accomplishes his aim of giving the necessary theoretical background in order to both understand and build algorithms for the computation of elementary functions (such as sine, cosine, exponential, logarithms), that are the most commonly used mathematical functions. Hardware- as well as software-oriented algorithms are presented, together with a pertinent analysis of accurate floating-point implementations…Good examples are always chosen in order to introduce or to illustrate the methods, following the given cases. The book is very well structured…"   —Analele Stiintifice ale Universitatii “Al. I. Cuza” din Iasi --This text refers to an alternate Hardcover edition.

From the Back Cover

"An important topic, which is on the boundary between numerical analysis and computer science…. I found the book well written and containing much interesting material, most of the time disseminated in specialized papers published in specialized journals difficult to find. Moreover, there are very few books on these topics and they are not recent." –Numerical Algorithms (review of the first edition) This unique book provides concepts and background necessary to understand and build algorithms for computing the elementary functions—sine, cosine, tangent, exponentials, and logarithms. The author presents and structures the algorithms, hardware-oriented as well as software-oriented, and also discusses issues related to accurate floating-point implementation. The purpose is not to give "cookbook recipes" that allow one to implement a given function, but rather to provide the reader with tools necessary to build or adapt algorithms for their specific computing environment. This expanded second edition contains a number of revisions and additions, which incorporate numerous new results obtained during the last few years. New algorithms invented since 1997—such as Matula’s bipartite method, another table-based method due to Ercegovac, Lang, Tisserand, and Muller—as well as new chapters on multiple-precision arithmetic and examples of implementation have been added. In addition, the section on correct rounding of elementary functions has been fully reworked, also in the context of new results. Finally, the introductory presentation of floating-point arithmetic has been expanded, with more emphasis given to the use of the fused multiply-accumulate instruction. The book is an up-to-date presentation of information needed to understand and accurately use mathematical functions and algorithms in computational work and design. Graduate and advanced undergraduate students, professionals, and researchers in scientific computing, numerical analysis, software engineering, and computer engineering will find the book a useful reference and resource. --This text refers to an alternate Hardcover edition.

Product Details

• Hardcover: 228 pages
• Publisher: Birkhauser; 1 edition (July 15, 1997)
• Language: English
• ISBN-10: 081763990X
• ISBN-13: 978-0817639907
• Product Dimensions: 10.3 x 7.3 x 0.6 inches
• Shipping Weight: 1.4 pounds
• Average Customer Review: 5.0 out of 5 stars  See all reviews (5 customer reviews)
• Amazon Best Sellers Rank: #4,078,246 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

5 of 5 people found the following review helpful:

5.0 out of 5 stars When every bit matters, June 16, 2007

By 

wiredweird "wiredweird" (Earth, or somewhere nearby) - See all my reviews
(HALL OF FAME REVIEWER)    (TOP 500 REVIEWER)   

Amazon Verified Purchase

This review is from: Elementary Functions: Algorithms and Implementation (Hardcover)

Most people use floating point arithmetic in a fairly cavalier way. They treat double precision numbers as exact. And, although people use commercial libraries for transcendentals and the like, they seem unconcerned when they need to implement an offbeat function or approximation. Everyone knows the Taylor series for exp(x), for example, so how hard could it be to code that up? (Answer: easy to code, and equally easy to do very badly.)

In fact, IEEE standard arithmetic can not even represent 1/3 exactly. (If that's news to you, or if you think the difference doesn't matter, you should back off and find some introductory material before attacking this book). Also, orthogonal polynomials will give better accuracy and more controllable error than Taylor series, for polynomial approximations of given degree - over a decimal digit more accuracy, in a project I worked on recently. The first three chapters go over those basics, then get into the book's real content.

The next chapters address table-based methods - and tables appear at one point or another in many implementations.Then the author presents iterative techniques for square roots (and 1/sqrt, which is often more convenient), logs exponentials, and trig functions. Although accuracy is paramount, these algorithms also emphasize fast convergence using inexpensive operations. The next section, on shift-and-add algorithms, presents advanced, accurate, efficient algorithms including CORDIC. This section requires close attention, since this book is about principles rather than cut-and-paste coding, so people without immediate implementation needs might come back to it to give it the effort it requires. The book's last section deals with range reduction, i.e. converting the problem to a more tightly bounded one, where the algorithm's behavior can be better undestood and controlled. It also deals with rounding and other quirky cases in floating point arithmetic.

This book isn't for everyone - in fact, not many people these days need to implement "library" functions on their own. As a result, knowledge of implementing them well is increasingly scarce. If you end up in the unusual position of having to implement them yourself, possibly using an exotic computing technology, then this book will help you get the last possible bit of accuracy, and to get it as fast as possible.

-- wiredweird

3 of 3 people found the following review helpful:

5.0 out of 5 stars Clear and complete, January 3, 2007

By 

Mauro Fiorentini (Milano, Italy) - See all my reviews
(REAL NAME)   

This review is from: Elementary Functions: Algorithms and Implementation (Hardcover)

The book clearly explains the most important algorithms used by computers to compute many mathematical functions, with plenty of actual examples.
It is not a list of algorithms and tables, but rather a recipe book; actual computation of values and tables is left to the reader, better equipped with some numerical analysis package.
Despite the title, the methods can be applied (with some effort) to a broad set of functions (including many that are not usually considered "elementary", like Bessel or Gudermannian functions).
An extensive bibliography is included.
A must for those who are involved in designing and implementing such functions for a computer, but also an enjoyable reading for those who wonder how some functions can be computed.

1 of 1 people found the following review helpful:

5.0 out of 5 stars Kindle version difficult to read, December 13, 2010

By 

Ed Karrels - See all my reviews

Amazon Verified Purchase

This review is from: Elementary Functions: Algorithms and Implementation (Kindle Edition)

There are many figures and math equations in this book, and the way the book was digitized, many of them are difficult to read. Portions of letters and numbers are missing, equations are not always in the proper order with their associated text, and figures look blurry. It's as if you're referencing a bad photocopy. The content of the book is excellent, however, thus the 5-star review. Just get the paper version and avoid the Kindle version.