Computer Arithmetic Algorithms Second Edition

This text explains the fundamental principles of algorithms available for performing arithmetic operations on digital computers. These include basic arithmetic operations like addition, subtraction, multiplication, and division in fixed-point and floating-point number systems as well as more complex operations such as square root extraction and evaluation of exponential, logarithmic, and trigonometric functions. The algorithms described are independent of the particular technology employed for their implementation. Numerical examples illustrate the working of the algorithms presented and explain the concepts behind the algorithms without relying on gate diagrams. This new edition includes sections on floating-point adders, floating-point exceptions, general carry-look-ahead adders, prefix adders, Ling adders, and fused multiply-add units. New algorithms and implementations have been added to almost all chapters. Cover -- Half Title -- Title Page -- Copyright Page -- Dedication -- Table of Contents -- FORWORD TO THE SECOND EDITION -- PREFACE -- 1: CONVENTIONAL NUMBER SYSTEMS -- 1.1 The Binary Number System -- 1.2 Machine Representations of Numbers -- 1.3 Radix Conversions -- 1.4 Representations of Negative Numbers -- 1.5 Addition and Subtraction -- 1.6 Arithmetic Shift Operations -- 1.7 Exercises -- 1.8 References -- 2: UNCONVENTIONAL FIXED-RADIX NUMBER SYSTEMS -- 2.1 Negative-Radix Number Systems -- 2.2 A General Class of Fixed-Radix Number Systems -- 2.3 Signed-Digit Number Systems -- 2.4 Binary SD Numbers -- 2.5 Exercises -- 2.6 References -- 3: SEQUENTIAL ALGORITHMS FOR MULTIPLICATION AND DIVISION -- 3.1 Sequential Multiplication -- 3.2 Sequential Division -- 3.3 Nonrestoring Division -- 3.4 Square Root Extraction -- 3.5 Exercises -- 3.6 References -- 4: BINARY FLOATING-POINT NUMBERS -- 4.1 Preliminaries -- 4.2 Floating-Point Operations -- 4.3 Choice of Floating-Point Representation -- 4.4 The IEEE Floating-Point Standard -- 4.5 Round-off Schemes -- 4.6 Guard Digits -- 4.7 Floating-Point Adders -- 4.8 Exceptions -- 4.9 Round-off Errors and Their Accumulation -- 4.10 Exercises -- 4.11 References -- 5: FAST ADDITION -- 5.1 Ripple-Carry Adders -- 5.2 Carry-Look-Ahead Adders -- 5.3 Conditional Sum Adders -- 5.4 Optimality of Algorithms and Their Implementations -- 5.5 Carry-Look-Ahead Addition Revisited -- 5.6 Prefix Adders -- 5.7 Ling Adders -- 5.8 Carry-Select Adders -- 5.9 Carry-Skip Adders -- 5.10 Hybrid Adders -- 5.11 Carry-Save Adders -- 5.12 Pipelining of Arithmetic Operations -- 5.13 Exercises -- 5.14 References -- 6: HIGH-SPEED MULTIPLICATION -- 6.1 Reducing the Number of Partial Products -- 6.2 Implementing Large Multipliers Using Smaller Ones -- 6.3 Accumulating the Partial Products -- 6.4 Alternative Techniques for Partial Product Accumulation 6.5 Fused Multiply-Add Unit -- 6.6 Array Multipliers -- 6.7 Optimality of Multiplier Implementations -- 6.8 Exercises -- 6.9 References -- 7: FAST DIVISION -- 7.1 SRT Division -- 7.2 High-Radix Division -- 7.3 Speeding Up the Division Process -- 7.4 Array Dividers -- 7.5 Fast Square Root Extraction -- 7.6 Exercises -- 7.7 References -- 8: DIVISION THROUGH MULTIPLICATION -- 8.1 Division by Convergence -- 8.2 Division by Reciprocation -- 8.3 Exercises -- 8.4 References -- 9: EVALUATION OF ELEMENTARY FUNCTIONS -- 9.1 The Exponential Function -- 9.2 The Logarithm Function -- 9.3 The Trigonometric Functions -- 9.4 The Inverse Trigonometric Functions -- 9.5 The Hyperbolic Functions -- 9.6 Bounds on the Approximation Error -- 9.7 Speed-up Techniques -- 9.8 Other Techniques for Evaluating Elementary Functions -- 9.9 Exercises -- 9.10 References -- 10: LOGARITHMIC NUMBER SYSTEMS -- 10.1 Sign-Logarithm Number Systems -- 10.2 Arithmetic Operations -- 10.3 Comparison to Binary Floating-Point Numbers -- 10.4 Conversions to/from Conventional Representations -- 10.5 Exercises -- 10.6 References -- 11: THE RESIDUE NUMBER SYSTEM -- 11.1 Preliminaries -- 11.2 Arithmetic Operations -- 11.3 The Associated Mixed-Radix System -- 11.4 Conversion of Numbers from/to the Residue System -- 11.5 Selecting the Moduli -- 11.6 Error Detection and Correction -- 11.7 Exercises -- 11.8 References -- INDEX Concentrating on the underlying principles, this book explains the algorithms used in arithmetic operations on digital computers. It identifies the similarities between the different algorithms and provides guidance for selecting the appropriate algorithms for a given technology. Chapters cover conventional number systems, unconventional fixed-radix number systems, sequential algorithms for multiplication and division, binary floating-point numbers, fast addition, high-speed multiplication, fast division, division through multiplication, the evaluations of elementary functions, logarithmic number systems, and the residue number system

This text explains the fundamental principles of algorithms available for performing arithmetic operations on digital computers. These include basic arithmetic operations like addition, subtraction, multiplication, and division in fixed-point and floating-point number systems as well as more complex operations such as square root extraction and evaluation of exponential, logarithmic, and trigonometric functions. The algorithms described are independent of the particular technology employed for their implementation.

In conventional digital computers, integers are represented as binary numbers of fixed length.