Very few books do justice to material that is suitable for both professional software engineers and graduate students. This book does just that, without losing its focus or stressing one audience over the other. As the authors make clear, this book is about algorithms for arithmetic (and not hardware considerations and implementations); this focus allows them to cover integer arithmetic, modular arithmetic, and floating-point arithmetic broadly and in detail. The notes and references at the end of each chapter guide readers to more details, and provide a historical backdrop for each major topic.
We can conceptually group the book’s five chapters into two broad and tightly integrated categories: arithmetic algorithms and programming language packages. The first category devotes chapters to integer arithmetic, modular arithmetic and the fast Fourier transform (FFT), floating-point arithmetic, and the evaluation of elementary and special functions. The final chapter constitutes a category of its own: implementation packages.
The opening chapter on integer arithmetic is characteristic of the book as a whole. Its treatment of division, for example, illustrates the depth of presentation and the narrative strategies that the authors employ throughout. The chapter opens with a brief discussion of the range of division operations it will cover, which serves as an outline for what follows. It then presents a naive algorithm for division in a sparsely annotated, language-independent form. Although the intended audience likely has a high degree of sophistication in reading algorithms in an abstract form, and although the algorithm does include an annotation, more robust commentary would help with readability and reduce the overhead of understanding the semantics of the algorithm.
Complementing the algorithm is a proof of its correctness, some analysis of its complexity, and a brief discussion of some variations on it and its drawbacks. The authors then present more sophisticated division algorithms, such as recursive and unbalanced division, along with proofs of their correctness, to round out the discussion. Other topics treated in this chapter are multiplication, roots, greatest common divisor, and base conversions. The exercises at the end of the chapter will push readers to deepen their understanding of the material by proving some characteristics of the material covered and by designing algorithms. The notes and references are excellent introductions to the literature on integer arithmetic, and they enable readers to acquire some familiarity with the historical development of the subject.
The chapter on modular arithmetic and the FFT presents both classical and more contemporary representations of: the remainders of division; the theoretical setting for the FFT; implementations of the FFT; modular multiplication, division, and exponentiation; and the Chinese remainder algorithm. The chapter links conceptually to the first chapter in its discussion of the connection between modular and polynomial arithmetic. The discussion of Montgomery’s algorithm for modular arithmetic is well developed in that the authors explain the rationale for the algorithm and its extensions.
Inclusion of the Chinese remainder algorithm is one of the many implicit connections that would allow this work to be used in a graduate course in computer science. Students could flesh out its treatment here in a high-level language, to provide an underlying narrative of the algorithm.
The chapter on floating-point arithmetic, as one would expect, parallels the first chapter on integer arithmetic in treating fundamental arithmetic operations and base conversions, and determining square roots. The authors, as they do throughout, explicitly establish links to operations on integers. Rounding is one topic that distinguishes operations on floating-point numbers from operations on integers, and the authors devote proportionate space to it. The treatment is especially strong in introducing the theoretical issues that attend rounding and that govern the construction of algorithms.
The book concludes with two chapters that deepen the understanding of the material presented earlier by discussing some functions and outlining available software tools. The chapter on elementary and special function evaluation revisits some of the material presented earlier, but does so at a higher level. The chapter devotes considerable space to Newton’s method as it applies to floating-point computations. In particular, the chapter covers inverse roots, power series, and functional inverses. The chapter concludes with a discussion of argument reduction, power series, asymptotic expansions, continued fractions, and recurrence relations.
The narrative portion of the book ends with a short treatment of relevant software packages that contain useful libraries and online documentation. The authors could profitably develop this chapter by comparing the strengths and weaknesses of the software mentioned.
Readers such as software engineers and graduate students who are looking for a broad understanding of modern computer arithmetic will find it here, but a full treatment of the topic is beyond the mission of this work.
