book

The End of Error

Name: The End of Error
Author: John L. Gustafson
ISBN: 9781482239874

by John L. Gustafson

June 2017

Intermediate to advanced

416 pages

12h 30m

English

Chapman and Hall/CRC

Read now

Unlock full access

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 answers1.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 plots2.2 Negative numbers2.3 Fixed point format2.4 Floating point format, almost2.5 What about infinity and NaN? Improving on IEEE rules

Chapter 3 The “original sin” of computer arithmetic
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
Chapter 4 The complete unum format
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
Chapter 5 Hidden scratchpads and the three layers
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”?
Chapter 6 Information per bit
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?
Chapter 7 Fixed-size unum storage
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
Chapter 8 Comparison operations
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
Chapter 9 Add/subtract, and the unbiased rounding myth
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
Chapter 10 Multiplication and division
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
Chapter 11 Powers
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
Chapter 12 Other important unary operations
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
Chapter 13 Fused operations (single-use expressions)
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
Chapter 14 Trial runs: Unums face challenge calculations
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
Part 1 Summary
Part 2 A New Way to Solve: The Ubox
Chapter 15 The other kind of error
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”
Chapter 16 Avoiding interval arithmetic pitfalls
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
Chapter 17 What does it mean to “solve” an equation?
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
Chapter 18 Permission to guess
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
Chapter 19 Pendulums done correctly
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
Chapter 20 The two-body problem (and beyond)
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
Chapter 21 Calculus considered evil: Discrete physics
21.1 Continuum versus discrete physics21.2 The discrete version of a vibrating string21.3 The single-atom gas21.4 Structural analysis
Chapter 22 The end of error
Glossary
Appendix A: Glossary of unum functions
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
Appendix B: Glossary of ubox 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
Appendix C: Algorithm listings for Part 1
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
Appendix D: Algorithm listings for Part 2
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
For Further Reading
Index

Content preview from The End of Error

14 Trial runs: Unums face challenge calculations

Images

Berkeley Professor William Kahan, primary architect of the IEEE 754 Standard.

14.1 Floating point II: The wrath of Kahan

Berkeley professor William Kahan is skilled at finding examples of mathematical questions to which floating point provides grossly incorrect answers … as well as examples where proposed alternatives are even worse than floats. Can unums withstand the wrath of Kahan?

Here is one of Kahan’s favorite examples: Iterate

$u_{i + 2} = 111 - \frac{1130}{u_{j + 1}} + \frac{3000}{u_{j} u_{j + 1}}$

starting with u₀ = 2, u₁ = -4. With floats, the iteration starts to converge to 6, but then heads for 100 instead even though 6 is ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

The Hidden Cost of AI-Assisted Creativity

Publisher Resources

ISBN: 9781482239867

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

The End of Error

by John L. Gustafson

14 Trial runs: Unums face challenge calculations

14.1 Floating point II: The wrath of Kahan

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.