Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Finite precision number systems and arithmetic
Kornerup P., Matula D., Cambridge University Press, New York, NY, 2010. 716 pp. Type: Book (978-0-521761-35-2)
Date Reviewed: Jun 10 2011

Every undergraduate computer engineering or computer science curriculum has at least one course in computer architecture that includes a section that explains how computers do arithmetic. At this introductory level, authors usually use diagrams of gates rather than algebraic expressions to describe the operations. This book, however, is designed to be a complete guide to computer arithmetic, and thus depends on algebraic notation and methods. To this end, the authors first develop a significant set of results and methods for radix polynomials, and then use that set to explain the wide range of algorithms that have been developed and implemented in computers.

As the authors state in the preface: “It is our belief that a detailed understanding of radix representation and conversion between these is of great importance when developing and/or implementing arithmetic algorithms.” The chapters cover radix polynomials, fixed-point addition/subtraction, multiplication, division, square roots, floating-point operations, modular arithmetic, and rational arithmetic.

By a radix polynomial, the authors mean an expression: ∑mi=ldiβi, where l<m, β is the radix, and the di are from a relatively small digit set D of integers. They investigate the properties of radix and digit set combinations, such as completeness and redundancy, and describe algorithms to convert from one combination to another. For a radix β, the digit set D is complete if, for every rational number v that has a finite expansion base β, there is a radix polynomial P in β and D such that P=v. D is redundant if there is more than one such P.

The chapter on addition begins with an abstract model that describes the representation of a generic add-and-carry algorithm. Starting with two addend polynomials P0 and Q0, in radix β and digit set D, the model algorithm constructs a sequence of pairs of polynomials (Pi, Qi) such that for i>0, P0+Q0Pi+Qi, where the “carry” digits of Pi are from a set Ci, and the “sum” digits of Qi are from D. The process ends when Pi=0. Then, Qi is the sum expressed in the original digit set D. This same approach can be used to describe add-and-carry algorithms where the digit sets of the addends or the sum are different.

Any such process can be characterized by digit addition tables for each step that define the digits for terms in (Pi+1, Qi+1) from the corresponding digits in (Pi, Qi). Moreover, an addition algorithm described by the process can be implemented by realizations of the addition tables (either by look-up procedures or with logic circuits).

Chapters on multiplication, division, and square roots follow the chapter on fixed-point addition. As in the earlier chapters, the authors first describe and algebraically analyze algorithms before any discussion of implementation. Since implementation of these operations depends at least indirectly on addition, they can be described in more general terms.

The chapter on floating-point arithmetic is much less algebraic. It describes the distribution of gaps on the real line between floating-point numbers, and various methods of rounding. The algorithms for addition/subtraction require shifting to align the radix point, and straightforward addition and further processing to achieve a normalized result. Floating-point multiplication and division are more straightforward since no shifting is required.

The final two chapters of the book are not directly related to the earlier ones. The chapter on modular arithmetic and residue representation systems begins with basic algorithms and implementations for modular addition, multiplication, and division. It then describes the representation of integers by their residues in several moduli, and presents algorithms for some arithmetic operations, such as conversion to and from residue-based representation to radix-based and the division of residue-based numbers.

The final chapter on rational arithmetic and fraction-based systems is “to a large extent based directly on a series of publications by the authors.” Rational arithmetic refers to arithmetic on rational operands, each represented as the ratio of two integers with results in the same form. For practical reasons, they must limit it to ratios where the numerator and denominator are bounded, and then define a mediant rounding so that the arithmetic is closed. The authors describe algorithms that produce mediant rounded results for basic arithmetic operations. They also discuss the representation of numbers by continued fractions.

This book is a detailed description of algorithms and implementations for computer arithmetic. It is more of a reference work than a text, but in the preface, the authors suggest a selection of chapters for a one-semester graduate course. The descriptions rely more on algebra and less on logic diagrams, so students should have some background in abstract algebra (such as groups, rings, and fields) but no more logic design theory than is found in a computer architecture course.

Each chapter ends with a bibliography and notes on the topics covered. Although the book is not organized with any view to history, these notes often indicate historically important results and researchers.

Reviewer:  Charles R. Crawford Review #: CR139133 (1110-0994)
Bookmark and Share
 
General (B.2.0 )
 
 
General (I.1.0 )
 
 
Mathematical Software (G.4 )
 
Would you recommend this review?
yes
no
Other reviews under "General": Date
Adders
Takagi N., Tago H., Baugh C., Muroga S. In The VLSI handbook. Boca Raton, FL: CRC Press, Inc., 2000. Type: Book Chapter
Jan 15 2003
Improving SoC design quality through a reproducible design flow
Magarshack P. IEEE Design & Test of Computers 19(1): 76-83, 2002. Type: Article
Jun 9 2004
 An approximate algorithm for the multiple constant multiplications problem
Aksoy L., Gunes E.  Integrated circuits and system design (Proceedings of the Twenty-first Annual Symposium on Integrated Circuits and System Design, Gramado, Brazil, Sep 1-4, 2008)58-63, 2008. Type: Proceedings
Nov 19 2008
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy