book

The End of Error

by John L. Gustafson

June 2017

Intermediate to advanced

416 pages

12h 30m

English

Chapman and Hall/CRC

Read now

Unlock full access

1.1 Fewer bits. Better answers1.2 Why better arithmetic can save energy and power
2.1 A graphical view of bit strings: Value and closure plots2.2 Negative numbers2.3 Fixed point format2.4 Floating point format, almost2.5 What about infinity and NaN? Improving on IEEE rules

3.1 The acceptance of incorrect answers3.2 “Almost infinite” and “beyond infinity”3.3 No overflow, no underflow, and no rounding3.4 Visualizing ubit-enabled numbers
4.1 Overcoming the tyranny of fixed storage size4.2 The IEEE Standard float formats4.3 Unum format: Flexible range and precision4.4 How can appending extra bits save storage?4.5 Ludicrous precision? The vast range of unums4.6 Changing environment settings within a computing task4.7 The reference prototype4.8 Special values in a flexible precision environment4.9 Converting exact unums to real numbers4.10 A complete exact unum set for a small utag4.11 Inexact unums4.12 A visualizer for unum strings
5.1 The hidden scratchpad5.1.1 The Cray-1 supercomputer5.1.2 The original definition of the C language5.1.3 Coprocessors also try to be helpful5.1.4 IBM almost gets it right: The fused multiply-add5.1.5 Kulisch gets it right: The exact dot product (EDP)5.2 The unum layer5.2.1 The ubound5.2.2 Processor design for the u-layer5.3 The math layer5.3.1 The general bound, or “gbound”5.3.2 Who uses NaN? Sun Microsystems gets a nasty surprise5.3.3 An explosion of storage demand in the scratchpad?5.3.4 Traditional interval arithmetic. Watch out.5.3.5 Significance arithmetic5.3.6 Why endpoints must be marked open or closed5.4 The human layer5.4.1 Numbers as people perceive them5.4.2 Demands and concessions5.5 Moving between layers5.5.1 Defining the conversion function5.5.2 Testing the conversion function5.6 Summary of conversions between layers in the prototype5.7 Are floats “good enough for government work”?
6.1 Information as the reciprocal of uncertainty6.2 “Unifying” a bound to a single unum6.3 Unification in the prototype6.3.1 The option of lossy compression6.3.2 Intelligent unification6.3.3 Much ado about almost nothing and almost infinite6.4 Can ubounds save storage compared with traditional floats?
7.1 The Warlpiri unums7.2 The Warlpiri ubounds7.3 Hardware for unums: Faster than float hardware?7.3.1 General comments about the cost of handling exceptions7.3.2 Unpacked unum format and the “summary bits” idea
8.1 Less than, greater than8.1.1 Conceptual definition of ordering for general intervals8.1.2 Hardware design for “less than” and “greater than” tests8.2 Equal, nowhere equal, and “not nowhere equal”8.2.1 Conceptual definition of “equal” for general intervals8.2.2 Hardware approach for equal and “not nowhere equal”8.3 Intersection
9.1 Re-learning the addition table … for all real numbers9.1.1 Examples and tests of data motion9.1.2 Three-dimensional visualization of ubound addition9.1.3 Hardware design for unum addition and subtraction9.2 “Creeping crud” and the myth of unbiased rounding9.3 Automatic accuracy control and a simple unum math test
10.1 Multiplication requires examining each quadrant10.2 Hardware for unum multiplication10.2.1 Multiplies that fit the standard hardware approach10.2.2 Extended precision and the “complete accumulator”10.2.3 Really big multiplies10.3 Division introduces asymmetry in the arguments10.3.1 The “bad boy” of arithmetic10.3.2 Hardware for unum division
11.1 Square11.2 Square root11.3 Nested square roots and “ULP straddling”11.4 Taxing the scratchpad: Integers to integer powers11.5 A practice calculation of xy at low precision11.6 Practical considerations and the actual working routine11.6.1 Why the power function can be fast11.6.2 The prototype power function11.6.3 A challenge to the defenders of floats11.7 Exp(x) and “The Table-Maker’s Dilemma”11.7.1 Another dilemma caused by the dishonesty of rounding11.7.2 The prototype exponential function
12.1 Scope of the prototype12.2 Absolute value12.3 Natural logarithm, and a mention of log base 212.4 Trig functions: Ending the madness by degrees
13.1 Standardizing a set of fused operations13.2 Fused multiply-add and fused multiply-subtract13.3 Solving the paradox of slow arithmetic for complex numbers13.4 Unum hardware for the complete accumulator13.4.1 Cost within the unpacked unum environment13.4.2 Fused dot product and fused sums in the prototype13.4.3 Consistent results for parallel computing13.5 Other fused operations13.5.1 Not every pairing of operations should be fused13.5.2 Fused product13.5.3 Fused add-multiply13.5.4 Fused product ratio13.5.5 Fused norm, fused root dot product, and fused mean
14.1 Floating point II: The wrath of Kahan14.2 Rump’s royal pain14.3 The quadratic formula14.4 Bailey’s numerical nightmare14.5 Fast Fourier Transforms using unums
15.1 Sampling error15.2 The deeply unsatisfying nature of classical error bounds15.3 The ubox approach15.4 Walking the line15.5 A ubox connected-region example: Computing the unit circle area15.6 A definition of answer quality and computing “speed”15.7 Another Kahan booby trap: The “smooth surprise”
16.1 Useless error bounds16.2 The wrapping problem16.3 The dependency problem16.4 Intelligent standard library routines16.5 Polynomial evaluation without the dependency problem16.6 Other fused multiple-use expressions
17.1 Another break from traditional numerical methods17.2 A linear equation in one unknown, solved by inversion17.2.1 Inversion with unums and intervals17.2.2 Ubounds as coefficients17.3 “Try everything!” Exhaustive search of the number line17.3.1 The quadratic formula revisited17.3.2 To boldly split infinities: Try everything17.3.3 Highly adjustable parallelism17.4 The universal equation solver17.4.1 Methods that USUALLY work17.4.2 The general failure of the inversion method17.4.3 Inequality testing; finding extrema17.4.4 The “intractable” fallacy17.5 Solvers in more than one dimension17.6 Summary of the ubox solver approach
18.1 Algorithms that work for floats also work for unums18.2 A fixed-point problem18.3 Large systems of linear equations18.4 The last resort
19.1 The introductory physics approach19.2 The usual numerical approach19.3 Space stepping: A new source of massive parallelism19.4 It’s not just for pendulums
20.1 A differential equation with multiple dimensions20.1.1 Setting up a traditional simulation20.1.2 Trying a traditional method out on a single orbit20.1.3 What about interval arithmetic methods?20.2 Ubox approach: The initial space step20.2.1 Solving the chicken-and-egg puzzle20.2.2 First, bound the position20.3 The next starting point, and some state law enforcement20.4 The general space step20.5 The three-body problem20.6 The n-body problem and the galaxy colliders
21.1 Continuum versus discrete physics21.2 The discrete version of a vibrating string21.3 The single-atom gas21.4 Structural analysis
A.1 Environment and bit-extraction functionsA.2 ConstructorsA.3 Visualization functionsA.4 Conversion functionsA.5 Argument validity testsA.6 Helper functions for functions defined aboveA.7 Comparison operationsA.8 Arithmetic operationsA.9 Fused operations (single-use expressions)A.10 Some defined data valuesA.11 Auto-precision functions
B.1 ULP-related manipulationsB.2 Neighbor-finding functionsB.3 Ubox creation by splittingB.4 Coalescing ubox setsB.5 Ubox bounds, width, volumeB.6 Test operations on setsB.7 Fused polynomial evaluation and acceleration formulaB.8 The try-everything solverB.9 The guessing function
C.1 The set-the-environment functionC.2 Type-checking functionsC.3 The unum-to-float converter and supporting functionsC.4 The u-layer to general interval conversionsC.5 The real-to-unum or x" conversion functionC.6 Unification functions and supporting functionsC.7 The general interval to unum converterC.8 Comparison tests and ubound intersectionC.9 Addition and subtraction functionsC.10 Multiplication functionsC.11 Division routinesC.12 Automatic precision adjustment functionsC.13 Fused operations (single-use expressions)C.14 Square and square rootC.15 The power function xy and exp(x)C.16 Absolute value, logarithm, and trigonometry functionsC.17 The unum Fast Fourier Transform
D.1 ULP manipulation functionsD.2 Neighbor-finding functionsD.3 Ubox creation by splittingD.4 Coalescing ubox setsD.5 Ubox bounds, width, volumesD.6 Test operations on setsD.7 Fused polynomial evaluation and acceleration formulaD.8 The try-everything solverD.9 The guess function

Content preview from The End of Error

Appendix D Algorithm listings for Part 2

D.1 ULP manipulation functions

To manipulate multidimensional ubounds (that is, uboxes), we need support functions that promote and demote the fraction size and exponent size. These must be used with care since they affect the ULP size, but they are useful when we can determine which end of the ULP-wide interval moves and which end stays put. Since the first two routines require exact unums as input, nothing will happen to the value they represent; they simply decompress the fraction field or exponent field by one bit. The reason it is more complicated to promote the exponent field is because subnormals behave differently from normals, and there is also the possibility that exponent promotion causes ...