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