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.

Forword to the Second Edition

xi

Preface

xiii

Conventional Number Systems

1

(18)

The Binary Number System

1

(1)

Machine Representations of Numbers

2

(2)

Radix Conversions

4

(2)

Representations of Negative Numbers

6

(7)

Addition and Subtraction

13

(2)

Arithmetic Shift Operations

15

(1)

Exercises

16

(1)

References

17

(2)

Unconventional Fixed-Radix Number Systems

19

(16)

Negative-Radix Number Systems

19

(2)

A General Class of Fixed-Radix Number Systems

21

(2)

Signed-Digit Number Systems

23

(4)

Binary SD Numbers

27

(5)

Exercises

32

(1)

References

33

(2)

Sequential Algorithms for Multiplication and Division

35

(18)

Sequential Multiplication

35

(4)

Sequential Division

39

(3)

Nonrestoring Division

42

(6)

Square Root Extraction

48

(2)

Exercises

50

(2)

References

52

(1)

Binary Floating-Point Numbers

53

(40)

Preliminaries

53

(6)

Floating-Point Operations

59

(6)

Choice of Floating-Point Representation

65

(2)

The IEEE Floating-Point Standard

67

(4)

Round-off Schemes

71

(5)

Guard Digits

76

(5)

Floating-Point Adders

81

(3)

Exceptions

84

(3)

Round-off Errors and Their Accumulation

87

(2)

Exercises

89

(2)

References

91

(2)

Fast Addition

93

(48)

Ripple-Carry Adders

93

(2)

Carry-Look-Ahead Adders

95

(4)

Conditional Sum Adders

99

(3)

Optimality of Algorithms and Their Implementations

102

(4)

Carry-Look-Ahead Addition Revisited

106

(3)

Prefix Adders

109

(1)

Ling Adders

110

(3)

Carry-Select Adders

113

(3)

Carry-Skip Adders

116

(3)

Hybrid Adders

119

(5)

Carry-Save Adders

124

(8)

Pipelining of Arithmetic Operations

132

(3)

Exercises

135

(3)

References

138

(3)

High-Speed Multiplication

141

(40)

Reducing the Number of Partial Products

141

(8)

Implementing Large Multipliers Using Smaller Ones

149

Accumulating the Partial Products

145

(12)

Alternative Techniques for Partial Product Accumulation

157

(8)

Fused Multiply-Add Unit

165

(2)

Array Multipliers

167

(7)

Optimality of Multiplier Implementations

174

(2)

Exercises

176

(3)

References

179

(2)

Fast Division

181

(32)

SRT Division

181

(6)

High-Radix Division

187

(11)

Speeding Up the Division Process

198

(5)

Array Dividers

203

(3)

Fast Square Root Extraction

206

(3)

Exercises

209

(1)

References

210

(3)

Division Through Multiplication

213

(12)

Division by Convergence

213

(5)

Division by Reciprocation

218

(4)

Exercises

222

(1)

References

223

(2)

Evaluation of Elementary Functions

225

(22)

The Exponential Function

226

(3)

The Logarithm Function

229

(3)

The Trigonometric Functions

232

(3)

The Inverse Trigonometric Functions

235

(3)

The Hyperbolic Functions

238

(1)

Bounds on the Approximation Error

239

(2)

Speed-up Techniques

241

(2)

Other Techniques for Evaluating Elementary Functions

243

(1)

Exercises

244

(1)

References

245

(2)

Logarithmic Number Systems

247

(12)

Sign-Logarithm Number Systems

247

(2)

Arithmetic Operations

249

(3)

Comparison to Binary Floating-Point Numbers

252

(1)

Conversions to/from Conventional Representations

253

(2)

Exercises

255

(1)

References

256

(3)

The Residue Number System

259

(18)

Preliminaries

259

(2)

Arithmetic Operations

261

(3)

The Associated Mixed-Radix System

264

(2)

Conversion of Numbers from/to the Residue System

266

(1)

Selecting the Moduli

267

(2)

Error Detection and Correction

269

(5)

Exercises

274

(1)

References

275

(2)

Index

277

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Computer Arithmetic Algorithms, Second Edition

Summary

Table of Contents

Supplemental Materials