Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

The ulp — where it appears

The gap between two adjacent representable numbers at a given magnitude. It doubles at every power of two, so an error of one of them is a relative statement rather than an absolute one.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

[½, 1)[1, 2)[2, 4)0.5124gap 0.125gap 0.25 — twice as wide8 values per octavespacing doubles at each power of two

What a float can hold

The representable numbers are not a fine fuzz spread evenly over the line. They are evenly spaced inside each power-of-two interval and twice as far apart in the next one up, and almost everything else in this subject is a consequence of that one fact.

arithmetic · Floating-point 02505007501000250275300325350375additionsrunning totalround to nearest: nothing arrivesexactstochasticnearesta thousand additionshalf an ulp at 2561moves, round to nearest0moves, stochastic46relative error, nearest0.28relative error, stochastic0.0228 significand bits, unbounded exponenta flat line is not a small error

A coin flip that fixes the average

Add 0.1 to 256 a thousand times at eight significand bits and the answer is 256. Not approximately — the total never moves, not once, and no error bound says so. Round up one time in twenty instead of never, and it arrives at 348 against a true 356.

arithmetic · Rounding

Named alongside it

The objects these essays reach for when they reach for this one.

Error accumulationUnit roundoffFloating-pointHalf-precisionMachine epsilonRounding modesSignificandStagnationStochastic roundingSummation

All concepts