Part I Number Representation Parts Chapters 1 . Numbers and Arithmetic 2 . Representing Signed Numbers I . Number Representation 3 . Redundant Number Systems 4 . Residue Number Systems 5 . Basic Addition and Counting 6 . Carry-Lookahead Adders s I I . Addition / Subtraction n 7 . Variations in Fast Adders o ti 8 . Multioperand Addition a r e 9 . Basic Multiplication Schemes p O 1 0 . High-Radix Multipliers y I I I. Multiplication 1 1 . Tree and Array Multipliers r a 1 2 . Variations in Multipliers nt e m 1 3 . Basic Division Schemes e 1 4 . High-Radix Dividers El I V . Division 1 5 . Variations in Dividers 1 6 . Division by Convergence 1 7 . Floating-Point Reperesentations 1 8 . Floating-Point Operations V . Real Arithmetic 1 9 . Errors and Error Control 2 0 . Precise and Certifiable Arithmetic 2 1 . Square-Rooting Methods 2 2 . The CORDIC Algorithms V I . Function Evaluation 2 3 . Variations in Function Evaluation 2 4 . Arithmetic by Table Lookup 2 5 . High-Throughput Arithmetic 2 6 . Low-Power Arithmetic V I I . Implementation Topics 2 7 . Fault-Tolerant Arithmetic 22 88 .. PRaescto, nPfrigesueranbt,l ea nAdr iFthumtuerteic Appendix: Past, Present, and Future Mar. 2011 Computer Arithmetic, Number Representation Slide 1 About This Presentation This presentation is intended to support the use of the textbook Computer Arithmetic: Algorithms and Hardware Designs (Oxford U. Press, 2nd ed., 2010, ISBN 978-0-19-532848-6). It is updated regularly by the author as part of his teaching of the graduate course ECE 252B, Computer Arithmetic, at the University of California, Santa Barbara. Instructors can use these slides freely in classroom teaching and for other educational purposes. Unauthorized uses are strictly prohibited. © Behrooz Parhami Edition Released Revised Revised Revised Revised First Jan. 2000 Sep. 2001 Sep. 2003 Sep. 2005 Apr. 2007 Apr. 2008 Apr. 2009 Second Apr. 2010 Mar. 2011 Mar. 2011 Computer Arithmetic, Number Representation Slide 2 I Background and Motivation Number representation arguably the most important topic: • Effects on system compatibility and ease of arithmetic • 2’s-complement, redundant, residue number systems • Limits of fast arithmetic • Floating-point numbers to be covered in Chapter 17 Topics in This Part Chapter 1 Numbers and Arithmetic Chapter 2 Representing Signed Numbers Chapter 3 Redundant Number Systems Chapter 4 Residue Number Systems Mar. 2011 Computer Arithmetic, Number Representation Slide 3 “This can’t be right . . . It goes into the red!” Mar. 2011 Computer Arithmetic, Number Representation Slide 4 1 Numbers and Arithmetic Chapter Goals Define scope and provide motivation Set the framework for the rest of the book Review positional fixed-point numbers Chapter Highlights What goes on inside your calculator? Ways of encoding numbers in k bits Radices and digit sets: conventional, exotic Conversion from one system to another Dot notation: a useful visualization tool Mar. 2011 Computer Arithmetic, Number Representation Slide 5 Numbers and Arithmetic: Topics Topics in This Chapter 1.1 What is Computer Arithmetic? 1.2 Motivating Examples 1.3 Numbers and Their Encodings 1.4 Fixed-Radix Positional Number Systems 1.5 Number Radix Conversion 1.6 Classes of Number Representations Mar. 2011 Computer Arithmetic, Number Representation Slide 6 1.1 What is Computer Arithmetic? Pentium Division Bug (1994-95): Pentium’s radix-4 SRT algorithm occasionally gave incorrect quotient First noted in 1994 by Tom Nicely who computed sums of reciprocals of twin primes: 1/5 + 1/7 + 1/11 + 1/13 + . . . + 1/p + 1/(p + 2) + . . . Worst-case example of division error in Pentium: 1.333 820 44... Correct quotient 4 195 835 c = = 3 145 727 1.333 739 06... circa 1994 Pentium double FLP value; accurate to only 14 bits (worse than single!) Mar. 2011 Computer Arithmetic, Number Representation Slide 7 Top Ten Intel Slogans for the Pentium Humor, circa 1995 (in the wake of the floating-point division bug) • 9.999 997 325 It’s a FLAW, dammit, not a bug • 8.999 916 336 It’s close enough, we say so • 7.999 941 461 Nearly 300 correct opcodes • 6.999 983 153 You don’t need to know what’s inside • 5.999 983 513 Redefining the PC –– and math as well • 4.999 999 902 We fixed it, really • 3.999 824 591 Division considered harmful • 2.999 152 361 Why do you think it’s called “floating” point? • 1.999 910 351 We’re looking for a few good flaws • 0.999 999 999 The errata inside Mar. 2011 Computer Arithmetic, Number Representation Slide 8 Aspects of, and Topics in, Computer Arithmetic Hardware (our focus in this book) Software ––––––––––––––––––––––––––––––––––––––––––––––––– –––––––––––––––––––––––––––––––––––– Design of efficient digital circuits for Numerical methods for solving primitive and other arithmetic operations systems of linear equations, such as +, –, ×, ÷, √, log, sin, and cos partial differential eq’ns, and so on Issues: Algorithms Issues: Algorithms Error analysis Error analysis Speed/cost trade-offs Computational complexity Hardware implementation Programming Testing, verification Testing, verification General-purpose Special-purpose –––––––––––––––––––––– ––––––––––––––––––––––– Flexible data paths Tailored to application Fast primitive areas such as: operations like Digital filtering +, –, ×, ÷, √ Image processing Benchmarking Radar tracking Fig. 1.1 The scope of computer arithmetic. Mar. 2011 Computer Arithmetic, Number Representation Slide 9 1.2 A Motivating Example Using a calculator with √, x2, and xy functions, compute: u = √√ … √ 2 = 1.000 677 131 “1024th root of 2” v = 21/1024 = 1.000 677 131 Save u and v; If you can’t save, recompute values when needed x = (((u2)2)...)2 = 1.999 999 963 x' = u1024 = 1.999 999 973 y = (((v2)2)...)2 = 1.999 999 983 y' = v1024 = 1.999 999 994 Perhaps v and u are not really the same value w = v – u = 1 × 10–11 Nonzero due to hidden digits (u – 1) × 1000 = 0.677 130 680 [Hidden ... (0) 68] (v – 1) × 1000 = 0.677 130 690 [Hidden ... (0) 69] Mar. 2011 Computer Arithmetic, Number Representation Slide 10