The End of Error

The End of Error

by John L. Gustafson
Released June 2017
Publisher(s): Chapman and Hall/CRC
ISBN: 9781482239874

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

The Future of Numerical Computing

Written by one of the foremost experts in high-performance computing and the inventor of Gustafson’s Law, The End of Error: Unum Computing explains a new approach to computer arithmetic: the universal number (unum). The unum encompasses all IEEE floating-point formats as well as fixed-point and exact integer arithmetic. This new number type obtains more accurate answers than floating-point arithmetic yet uses fewer bits in many cases, saving memory, bandwidth, energy, and power.

A Complete Revamp of Computer Arithmetic from the Ground Up

Richly illustrated in color, this groundbreaking book represents a fundamental change in how to perform calculations automatically. It illustrates how this novel approach can solve problems that have vexed engineers and scientists for decades, including problems that have been historically limited to serial processing.

Suitable for Anyone Using Computers for Calculations

The book is accessible to anyone who uses computers for technical calculations, with much of the book only requiring high school math. The author makes the mathematics interesting through numerous analogies. He clearly defines jargon and uses color-coded boxes for mathematical formulas, computer code, important descriptions, and exercises.

Table of contents

  1. Cover Page
  2. Half Title Page
  3. Title Page
  4. Copyright Page
  5. Contents
  6. Preface
  7. Acknowledgments
  8. Part 1 A New Number Format: The Unum
    1. Chapter 1 Overview
      1. 1.1 Fewer bits. Better answers
      2. 1.2 Why better arithmetic can save energy and power
    2. Chapter 2 Building up to the unum format
      1. 2.1 A graphical view of bit strings: Value and closure plots
      2. 2.2 Negative numbers
      3. 2.3 Fixed point format
      4. 2.4 Floating point format, almost
      5. 2.5 What about infinity and NaN? Improving on IEEE rules
    3. Chapter 3 The “original sin” of computer arithmetic
      1. 3.1 The acceptance of incorrect answers
      2. 3.2 “Almost infinite” and “beyond infinity”
      3. 3.3 No overflow, no underflow, and no rounding
      4. 3.4 Visualizing ubit-enabled numbers
    4. Chapter 4 The complete unum format
      1. 4.1 Overcoming the tyranny of fixed storage size
      2. 4.2 The IEEE Standard float formats
      3. 4.3 Unum format: Flexible range and precision
      4. 4.4 How can appending extra bits save storage?
      5. 4.5 Ludicrous precision? The vast range of unums
      6. 4.6 Changing environment settings within a computing task
      7. 4.7 The reference prototype
      8. 4.8 Special values in a flexible precision environment
      9. 4.9 Converting exact unums to real numbers
      10. 4.10 A complete exact unum set for a small utag
      11. 4.11 Inexact unums
      12. 4.12 A visualizer for unum strings
    5. Chapter 5 Hidden scratchpads and the three layers
      1. 5.1 The hidden scratchpad
        1. 5.1.1 The Cray-1 supercomputer
        2. 5.1.2 The original definition of the C language
        3. 5.1.3 Coprocessors also try to be helpful
        4. 5.1.4 IBM almost gets it right: The fused multiply-add
        5. 5.1.5 Kulisch gets it right: The exact dot product (EDP)
      2. 5.2 The unum layer
        1. 5.2.1 The ubound
        2. 5.2.2 Processor design for the u-layer
      3. 5.3 The math layer
        1. 5.3.1 The general bound, or “gbound”
        2. 5.3.2 Who uses NaN? Sun Microsystems gets a nasty surprise
        3. 5.3.3 An explosion of storage demand in the scratchpad?
        4. 5.3.4 Traditional interval arithmetic. Watch out.
        5. 5.3.5 Significance arithmetic
        6. 5.3.6 Why endpoints must be marked open or closed
      4. 5.4 The human layer
        1. 5.4.1 Numbers as people perceive them
        2. 5.4.2 Demands and concessions
      5. 5.5 Moving between layers
        1. 5.5.1 Defining the conversion function
        2. 5.5.2 Testing the conversion function
      6. 5.6 Summary of conversions between layers in the prototype
      7. 5.7 Are floats “good enough for government work”?
    6. Chapter 6 Information per bit
      1. 6.1 Information as the reciprocal of uncertainty
      2. 6.2 “Unifying” a bound to a single unum
      3. 6.3 Unification in the prototype
        1. 6.3.1 The option of lossy compression
        2. 6.3.2 Intelligent unification
        3. 6.3.3 Much ado about almost nothing and almost infinite
      4. 6.4 Can ubounds save storage compared with traditional floats?
    7. Chapter 7 Fixed-size unum storage
      1. 7.1 The Warlpiri unums
      2. 7.2 The Warlpiri ubounds
      3. 7.3 Hardware for unums: Faster than float hardware?
        1. 7.3.1 General comments about the cost of handling exceptions
        2. 7.3.2 Unpacked unum format and the “summary bits” idea
    8. Chapter 8 Comparison operations
      1. 8.1 Less than, greater than
        1. 8.1.1 Conceptual definition of ordering for general intervals
        2. 8.1.2 Hardware design for “less than” and “greater than” tests
      2. 8.2 Equal, nowhere equal, and “not nowhere equal”
        1. 8.2.1 Conceptual definition of “equal” for general intervals
        2. 8.2.2 Hardware approach for equal and “not nowhere equal”
      3. 8.3 Intersection
    9. Chapter 9 Add/subtract, and the unbiased rounding myth
      1. 9.1 Re-learning the addition table … for all real numbers
        1. 9.1.1 Examples and tests of data motion
        2. 9.1.2 Three-dimensional visualization of ubound addition
        3. 9.1.3 Hardware design for unum addition and subtraction
      2. 9.2 “Creeping crud” and the myth of unbiased rounding
      3. 9.3 Automatic accuracy control and a simple unum math test
    10. Chapter 10 Multiplication and division
      1. 10.1 Multiplication requires examining each quadrant
      2. 10.2 Hardware for unum multiplication
        1. 10.2.1 Multiplies that fit the standard hardware approach
        2. 10.2.2 Extended precision and the “complete accumulator”
        3. 10.2.3 Really big multiplies
      3. 10.3 Division introduces asymmetry in the arguments
        1. 10.3.1 The “bad boy” of arithmetic
        2. 10.3.2 Hardware for unum division
    11. Chapter 11 Powers
      1. 11.1 Square
      2. 11.2 Square root
      3. 11.3 Nested square roots and “ULP straddling”
      4. 11.4 Taxing the scratchpad: Integers to integer powers
      5. 11.5 A practice calculation of xy at low precision
      6. 11.6 Practical considerations and the actual working routine
        1. 11.6.1 Why the power function can be fast
        2. 11.6.2 The prototype power function
        3. 11.6.3 A challenge to the defenders of floats
      7. 11.7 Exp(x) and “The Table-Maker’s Dilemma”
        1. 11.7.1 Another dilemma caused by the dishonesty of rounding
        2. 11.7.2 The prototype exponential function
    12. Chapter 12 Other important unary operations
      1. 12.1 Scope of the prototype
      2. 12.2 Absolute value
      3. 12.3 Natural logarithm, and a mention of log base 2
      4. 12.4 Trig functions: Ending the madness by degrees
    13. Chapter 13 Fused operations (single-use expressions)
      1. 13.1 Standardizing a set of fused operations
      2. 13.2 Fused multiply-add and fused multiply-subtract
      3. 13.3 Solving the paradox of slow arithmetic for complex numbers
      4. 13.4 Unum hardware for the complete accumulator
        1. 13.4.1 Cost within the unpacked unum environment
        2. 13.4.2 Fused dot product and fused sums in the prototype
        3. 13.4.3 Consistent results for parallel computing
      5. 13.5 Other fused operations
        1. 13.5.1 Not every pairing of operations should be fused
        2. 13.5.2 Fused product
        3. 13.5.3 Fused add-multiply
        4. 13.5.4 Fused product ratio
        5. 13.5.5 Fused norm, fused root dot product, and fused mean
    14. Chapter 14 Trial runs: Unums face challenge calculations
      1. 14.1 Floating point II: The wrath of Kahan
      2. 14.2 Rump’s royal pain
      3. 14.3 The quadratic formula
      4. 14.4 Bailey’s numerical nightmare
      5. 14.5 Fast Fourier Transforms using unums
    15. Part 1 Summary
  9. Part 2 A New Way to Solve: The Ubox
    1. Chapter 15 The other kind of error
      1. 15.1 Sampling error
      2. 15.2 The deeply unsatisfying nature of classical error bounds
      3. 15.3 The ubox approach
      4. 15.4 Walking the line
      5. 15.5 A ubox connected-region example: Computing the unit circle area
      6. 15.6 A definition of answer quality and computing “speed”
      7. 15.7 Another Kahan booby trap: The “smooth surprise”
    2. Chapter 16 Avoiding interval arithmetic pitfalls
      1. 16.1 Useless error bounds
      2. 16.2 The wrapping problem
      3. 16.3 The dependency problem
      4. 16.4 Intelligent standard library routines
      5. 16.5 Polynomial evaluation without the dependency problem
      6. 16.6 Other fused multiple-use expressions
    3. Chapter 17 What does it mean to “solve” an equation?
      1. 17.1 Another break from traditional numerical methods
      2. 17.2 A linear equation in one unknown, solved by inversion
        1. 17.2.1 Inversion with unums and intervals
        2. 17.2.2 Ubounds as coefficients
      3. 17.3 “Try everything!” Exhaustive search of the number line
        1. 17.3.1 The quadratic formula revisited
        2. 17.3.2 To boldly split infinities: Try everything
        3. 17.3.3 Highly adjustable parallelism
      4. 17.4 The universal equation solver
        1. 17.4.1 Methods that USUALLY work
        2. 17.4.2 The general failure of the inversion method
        3. 17.4.3 Inequality testing; finding extrema
        4. 17.4.4 The “intractable” fallacy
      5. 17.5 Solvers in more than one dimension
      6. 17.6 Summary of the ubox solver approach
    4. Chapter 18 Permission to guess
      1. 18.1 Algorithms that work for floats also work for unums
      2. 18.2 A fixed-point problem
      3. 18.3 Large systems of linear equations
      4. 18.4 The last resort
    5. Chapter 19 Pendulums done correctly
      1. 19.1 The introductory physics approach
      2. 19.2 The usual numerical approach
      3. 19.3 Space stepping: A new source of massive parallelism
      4. 19.4 It’s not just for pendulums
    6. Chapter 20 The two-body problem (and beyond)
      1. 20.1 A differential equation with multiple dimensions
        1. 20.1.1 Setting up a traditional simulation
        2. 20.1.2 Trying a traditional method out on a single orbit
        3. 20.1.3 What about interval arithmetic methods?
      2. 20.2 Ubox approach: The initial space step
        1. 20.2.1 Solving the chicken-and-egg puzzle
        2. 20.2.2 First, bound the position
      3. 20.3 The next starting point, and some state law enforcement
      4. 20.4 The general space step
      5. 20.5 The three-body problem
      6. 20.6 The n-body problem and the galaxy colliders
    7. Chapter 21 Calculus considered evil: Discrete physics
      1. 21.1 Continuum versus discrete physics
      2. 21.2 The discrete version of a vibrating string
      3. 21.3 The single-atom gas
      4. 21.4 Structural analysis
    8. Chapter 22 The end of error
  10. Glossary
  11. Appendix A: Glossary of unum functions
    1. A.1 Environment and bit-extraction functions
    2. A.2 Constructors
    3. A.3 Visualization functions
    4. A.4 Conversion functions
    5. A.5 Argument validity tests
    6. A.6 Helper functions for functions defined above
    7. A.7 Comparison operations
    8. A.8 Arithmetic operations
    9. A.9 Fused operations (single-use expressions)
    10. A.10 Some defined data values
    11. A.11 Auto-precision functions
  12. Appendix B: Glossary of ubox functions
    1. B.1 ULP-related manipulations
    2. B.2 Neighbor-finding functions
    3. B.3 Ubox creation by splitting
    4. B.4 Coalescing ubox sets
    5. B.5 Ubox bounds, width, volume
    6. B.6 Test operations on sets
    7. B.7 Fused polynomial evaluation and acceleration formula
    8. B.8 The try-everything solver
    9. B.9 The guessing function
  13. Appendix C: Algorithm listings for Part 1
    1. C.1 The set-the-environment function
    2. C.2 Type-checking functions
    3. C.3 The unum-to-float converter and supporting functions
    4. C.4 The u-layer to general interval conversions
    5. C.5 The real-to-unum or x" conversion function
    6. C.6 Unification functions and supporting functions
    7. C.7 The general interval to unum converter
    8. C.8 Comparison tests and ubound intersection
    9. C.9 Addition and subtraction functions
    10. C.10 Multiplication functions
    11. C.11 Division routines
    12. C.12 Automatic precision adjustment functions
    13. C.13 Fused operations (single-use expressions)
    14. C.14 Square and square root
    15. C.15 The power function xy and exp(x)
    16. C.16 Absolute value, logarithm, and trigonometry functions
    17. C.17 The unum Fast Fourier Transform
  14. Appendix D: Algorithm listings for Part 2
    1. D.1 ULP manipulation functions
    2. D.2 Neighbor-finding functions
    3. D.3 Ubox creation by splitting
    4. D.4 Coalescing ubox sets
    5. D.5 Ubox bounds, width, volumes
    6. D.6 Test operations on sets
    7. D.7 Fused polynomial evaluation and acceleration formula
    8. D.8 The try-everything solver
    9. D.9 The guess function
  15. For Further Reading
  16. Index

Product information

  • Title: The End of Error
  • Author(s): John L. Gustafson
  • Release date: June 2017
  • Publisher(s): Chapman and Hall/CRC
  • ISBN: 9781482239874