The End of Error: Unum Computing, 1st Edition (Paperback) book cover

The End of Error

Unum Computing, 1st Edition

By John L. Gustafson

Chapman and Hall/CRC

416 pages | 191 Color Illus.

Purchasing Options:$ = USD
Paperback: 9781482239867
pub: 2015-02-05
SAVE ~$13.19
$65.95
$52.76
x
Hardback: 9781138402195
pub: 2017-07-27
SAVE ~$39.00
$195.00
$156.00
x
eBook (VitalSource) : 9781315161532
pub: 2017-06-26
from $32.98


FREE Standard Shipping!

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.

Reviews

"The author of the present book believes that it is time to supplement the century-old floating point arithmetic with something better: unum arithmetic. The book covers various operations with unum arithmetic and topics like polynomial evaluation, solving equations, two-body problem, etc. The appendices give a glossary of unum functions, ubox functions, and some algorithm listings."

Zentralblatt MATH 1320

"This book is an extraordinary reinvention of computer arithmetic and elementary numerical methods from the ground up. Unum arithmetic is an extension of floating point in which it is also possible to represent the open intervals between two floating point numbers. This leads to arithmetic that is algebraically much cleaner, without rounding error, overflow underflow, or negative zero, and with clean and consistent treatment of positive and negative infinity and NaN. These changes are not just marginal technical improvements. As the book fully demonstrates, they lead to what can only be described as a radical re-foundation of elementary numerical analysis, with new methods that are free of rounding error, fully parallelizable, fully portable, easier for programmers to master, and often more economical of memory, bandwidth, and power than comparable floating point methods. The book is exceptionally well written and produced and is illustrated on every page with full-color diagrams that perfectly communicate the material. Anyone interested in computer arithmetic or numerical methods must read this book. It is surely destined to be a classic."

—David Jefferson, Center for Advanced Scientific Computing, Lawrence Livermore National Laboratory

"John Gustafson’s book The End of Error presents the ideas of computer arithmetic in a very easy-to-read and understandable form. While the title is provocative, the content provides an illuminating discussion of the issues. The examples are engaging, well thought out, and simple to follow."

—Jack Dongarra, University Distinguished Professor, University of Tennessee

"John Gustafson presents a bold and brilliant proposal for a revolutionary number representation system, unum, for scientific (and potentially all other) computers. Unum’s main advantage is that computing with these numbers gives scientists the correct answer all the time. Gustafson is able to show that the universal number, or unum, encompasses all standard floating-point formats as well as fixed-point and exact integer arithmetic. The book is a call to action for the next stage: implementation and testing that would lead to wide-scale adoption."

—Gordon Bell, Researcher Emeritus, Microsoft Research

"Reading more and more in [John Gustafson’s] book became a big surprise. I had not expected such an elaborate and sound piece of work. It is hard to believe that a single person could develop so many nice ideas and put them together into a sketch of what perhaps might be the future of computing. Reading [this] book is fascinating."

—Ulrich Kulisch, Karlsruhe Institute of Technology, Germany

Table of Contents

A New Number Format: The Unum

Overview

Fewer bits. Better answers

Why better arithmetic can save energy and power

Building up to the unum format

A graphical view of bit strings: Value and closure plots

Negative numbers

Fixed point format

Floating point format, almost

What about infinity and NaN? Improving on IEEE rules

The "original sin" of computer arithmetic

The acceptance of incorrect answers

"Almost infinite" and "beyond infinity"

No overflow, no underflow, and no rounding

Visualizing ubit-enabled numbers

The complete unum format

Overcoming the tyranny of fixed storage size

The IEEE Standard float formats

Unum format: Flexible range and precision

How can appending extra bits save storage?

Ludicrous precision? The vast range of unums

Changing environment settings within a computing task

The reference prototype

Special values in a flexible precision environment

Converting exact unums to real numbers

A complete exact unum set for a small utag

Inexact unums

A visualizer for unum strings

Hidden scratchpads and the three layers

The hidden scratchpad

The unum layer

The math layer

The human layer

Moving between layers

Summary of conversions between layers in the prototype

Are floats "good enough for government work"?

Information per bit

Information as the reciprocal of uncertainty

"Unifying" a bound to a single ULP

Unification in the prototype

Can ubounds save storage compared with traditional floats?

Fixed-size unum storage

The Warlpiri unums

The Warlpiri ubounds

Hardware for unums: Faster than float hardware?

Comparison operations

Less than, greater than

Equal, nowhere equal, and "not nowhere equal"

Intersection

Add/subtract, and the unbiased rounding myth

Re-learning the addition table … for all real numbers

"Creeping crud" and the myth of unbiased rounding

Automatic error control and a simple test of unum math

Multiplication and division

Multiplication requires examining each quadrant

Hardware for unum multiplication

Division introduces asymmetry in the arguments

Powers

Square

Square root

Nested square roots and "ULP straddling"

Taxing the scratchpad: Integers to integer powers

A practice calculation of xy at low precision

Practical considerations and the actual working routine

Exp(x) and "The Table-Maker’s Dilemma"

Other important unary operations

Scope of the prototype

Absolute value

Natural logarithm, and a mention of log base 2

Trig functions: Ending the madness by degrees

Fused operations (single-use expressions)

Standardizing a set of fused operations

Fused multiply-add and fused multiply-subtract

Solving the paradox of slow arithmetic for complex numbers

Unum hardware for the complete accumulator

Other fused operations

Trial runs: Unums face challenge calculations

Floating point II: The wrath of Kahan

Rump’s royal pain

The quadratic formula

Bailey’s numerical nightmare

Fast Fourier Transforms using unums

A New Way to Solve: The Ubox

The other kind of error

Sampling error

The deeply unsatisfying nature of classical error bounds

The ubox approach

Walking the line

A ubox connected-region example: Computing the unit circle area

A definition of answer quality and computing "speed"

Another Kahan booby trap: The "smooth surprise"

Avoiding interval arithmetic pitfalls

Useless error bounds

The wrapping problem

The dependency problem

Intelligent standard library routines

Polynomial evaluation without the dependency problem

Other fused multiple-use expressions

What does it mean to "solve" an equation?

Another break from traditional numerical methods

A linear equation in one unknown, solved by inversion

"Try everything!" Exhaustive search of the number line

The universal equation solver

Solvers in more than one dimension

Summary of the ubox solver approach

Permission to guess

Algorithms that work for floats also work for unums

A fixed-point problem

Large systems of linear equations

The last resort

Pendulums done correctly

The introductory physics approach

The usual numerical approach

Space stepping: A new source of massive parallelism

It’s not just for pendulums

The two-body problem (and beyond)

A differential equation with multiple dimensions

Ubox approach: The initial space step

The next starting point, and some state law enforcement

The general space step

The three-body problem

The n-body problem and the galaxy colliders

Calculus considered evil: Discrete physics

Continuum versus discrete physics

The discrete version of a vibrating string

The single-atom gas

Structural analysis

The end of error

Glossary

For further reading

Appendix A: Glossary of unum functions

Appendix B: Glossary of ubox functions

Appendix C: Algorithm listings for Part 1

Appendix D: Algorithm listings for Part 2

Index

About the Author

Dr. John L. Gustafson is an applied physicist and mathematician. He is a former Director at Intel Labs and former Chief Product Architect at AMD. A pioneer in high-performance computing, he introduced cluster computing in 1985 and first demonstrated scalable massively parallel performance on real applications in 1988. This became known as Gustafson’s Law, for which he won the inaugural ACM Gordon Bell Prize. He is also a recipient of the IEEE Computer Society’s Golden Core Award. Find more details on his website.

About the Series

Chapman & Hall/CRC Computational Science

Learn more…

Subject Categories

BISAC Subject Codes/Headings:
COM000000
COMPUTERS / General
MAT004000
MATHEMATICS / Arithmetic
MAT021000
MATHEMATICS / Number Systems