Numbers and Computers

This is a book about numbers and how those numbers are represented in and operated on by computers. It is crucial that developers understand this area because the numerical operations allowed by computers, and the limitations of those operations, especially in the area of floating point math, affect virtually everything people try to do with computers. This book aims to fill this gap by exploring, in sufficient but not overwhelming detail, just what it is that computers do with numbers. Divided into two parts, the first deals with standard representations of integers and floating point numbers, while the second examines several other number representations. Details are explained thoroughly, with clarity and specificity. Each chapter ends with a summary, recommendations, carefully selected references, and exercises to review the key points. Topics covered include interval arithmetic, fixed-point numbers, big integers and rational arithmetic. This new edition has three new chapters: Pitfalls of Floating-Point Numbers (and How to Avoid Them), Arbitrary Precision Floating Point, and Other Number Systems. This book is for anyone who develops software including software engineers, scientists, computer science students, engineering students and anyone who programs for fun. Preface to the Second Edition 6 Preface 7 Who Should Read This Book 7 How to Use This Book 8 Acknowledgments 8 Contents 9 Part I Standard Representations 12 1 Number Systems 13 1.1 Representing Numbers 13 1.2 The Big Three (and One Old Guy) 18 1.3 Converting Between Number Bases 20 1.4 Chapter Summary 26 Exercises 26 References 27 2 Integers 28 2.1 Bits, Nibbles, Bytes, and Words 28 2.2 Unsigned Integers 30 2.2.1 Representation 30 2.2.2 Storage in Memory: Endianness 31 2.3 Operations on Unsigned Integers 34 2.3.1 Bitwise Logical Operations 34 2.3.2 Testing, Setting, Clearing, and Toggling Bits 39 2.3.3 Shifts and Rotates 42 2.3.4 Comparisons 46 2.3.5 Arithmetic 50 2.3.6 Square Roots 61 2.4 What About Negative Integers? 63 2.4.1 Sign-Magnitude 63 2.4.2 One's Complement 64 2.4.3 Two's Complement 64 2.5 Operations on Signed Integers 65 2.5.1 Comparison 65 2.5.2 Arithmetic 67 2.6 Binary-Coded Decimal 76 2.6.1 Introduction 76 2.6.2 Arithmetic with BCD 78 2.6.3 Conversion Routines 79 2.6.4 Other BCD Encodings 82 2.7 Chapter Summary 85 Exercises 86 References 88 3 Floating Point 89 3.1 Floating-Point Numbers 89 3.2 An Exceedingly Brief History of Floating-Point Numbers 92 3.3 Comparing Floating-Point Representations 93 3.4 IEEE 754 Floating-Point Representations 97 3.5 Rounding Floating-Point Numbers (IEEE 754) 105 3.6 Comparing Floating-Point Numbers (IEEE 754) 108 3.7 Basic Arithmetic (IEEE 754) 110 3.8 Handling Exceptions (IEEE 754) 113 3.9 Floating-Point Hardware (IEEE 754) 116 3.10 Binary Coded Decimal Floating-Point Numbers 118 3.11 Chapter Summary 121 Exercises 122 References 123 4 Pitfalls of Floating-Point Numbers (and How to Avoid Them) 124 4.1 What Pitfalls? 124 4.2 Some Experiments 126 4.3 Avoiding the Pitfalls 137 4.4 Chapter Summary 141 Exercises 142 References 142 Part II Other Representations 143 5 Big Integers and Rational Arithmetic 144 5.1 What is a Big Integer? 144 5.2 Representing Big Integers 145 5.3 Arithmetic with Big Integers 151 5.4 Alternative Multiplication and Division Routines 163 5.5 Implementations 172 5.6 Rational Arithmetic with Big Integers 176 5.7 When to Use Big Integers and Rational Arithmetic 182 5.8 Chapter Summary 185 Exercises 185 References 186 6 Fixed-Point Numbers 188 6.1 Representation (Q Notation) 188 6.2 Arithmetic with Fixed-Point Numbers 193 6.3 Trigonometric and Other Functions 199 6.4 An Emerging Use Case 209 6.5 When to Use Fixed-Point Numbers 216 6.6 Chapter Summary 217 Exercises 217 References 218 7 Decimal Floating Point 219 7.1 What is Decimal Floating-Point? 219 7.2 The IEEE 754-2008 Decimal Floating-Point Format 220 7.3 Decimal Floating-Point in Software 229 7.4 Thoughts on Decimal Floating-Point 236 7.5 Chapter Summary 237 Exercises 238 References 238 8 Interval Arithmetic 239 8.1 Defining Intervals 239 8.2 Basic Operations 241 8.3 Functions and Intervals 257 8.4 Implementations 262 8.5 Thoughts on Interval Arithmetic 266 8.6 Chapter Summary 267 Exercises 267 References 267 9 Arbitrary Precision Floating-Point 269 9.1 What is Arbitrary Precision Floating-Point? 269 9.2 Representing Arbitrary Precision Floating-Point Numbers 269 9.3 Basic Arithmetic with Arbitrary Precision Floating-Point Numbers 274 9.4 Comparison and Other Methods 277 9.5 Trigonometric and Transcendental Functions 278 9.6 Arbitrary Precision Floating-Point Libraries 282 9.7 Thoughts on Arbitrary Precision Floating-Point 294 9.8 Chapter Summary 295 Exercises 295 References 296 10 Other Number Systems 297 10.1 Introduction 297 10.2 Logarithmic Number System 297 10.3 Double-Base Number System 311 10.4 Residue Number System 328 10.5 Redundant Signed-Digit Number System 336 10.6 Chapter Summary 343 Exercises 344 References 345 Index 347 "This is a book about numbers and how those numbers are represented in and operated on by computers. It is crucial that developers understand this area because the numerical operations allowed by computers, and the limitations of those operations, especially in the area of floating point math, affect virtually everything people try to do with computers. This book aims to fill this gap by exploring, in sufficient but not overwhelming detail, just what it is that computers do with numbers. Divided into two parts, the first deals with standard representations of integers and floating point numbers, while the second details several other number representations. Each chapter ends with exercises to review the key points. Topics covered include interval arithmetic, fixed-point numbers, floating point numbers, big integers and rational arithmetic. This book is for anyone who develops software including software engineerings, scientists, computer science students, engineering students and anyone who programs for fun." -- Publisher's website This is a book about numbers and how those numbers are represented in and operated on by computers. Of course, numbers are fundamental to how computers operate because, in the end, everything a computer works with is a number. It is crucial that people who develop a code understand this area becasue the numerical operations allowed by computers and the limitations of those operations, especially in the area of floating point math, affect virtually everything people try to do with computers. This book aims to help by exploring, in sufficient, but not overwhelming, detail, just what it is that computers do with numbers. From preface Front Matter....Pages i-xiii Front Matter....Pages 1-1 Number Systems....Pages 3-17 Integers....Pages 19-79 Floating Point....Pages 81-115 Pitfalls of Floating-Point Numbers (and How to Avoid Them)....Pages 117-135 Front Matter....Pages 137-137 Big Integers and Rational Arithmetic....Pages 139-182 Fixed-Point Numbers....Pages 183-213 Decimal Floating Point....Pages 215-234 Interval Arithmetic....Pages 235-264 Arbitrary Precision Floating-Point....Pages 265-292 Other Number Systems....Pages 293-342 Back Matter....Pages 343-346 This book is about numbers and how they are represented and manipulated by computers. In this second edition, we expand on the coverage of the first edition by adding three new chapters and new material to several sections.