Numerical Linear Algebra
where the algebra stops being the arithmetic
Generator

Relative error of two algebraically identical expressions for (1 − cos x)/x², in binary64

One function in the arith library, called 11 times across 5 essays. Below: what it draws at its defaults, what it draws at every value an essay asks for, the 13 claims it put to the test while drawing them, and where it stands against the rule this site is named for.

At its defaults it draws relative error of two algebraically identical expressions for (1 − cos x)/x², in binary64. A log–log plot of relative error against x, in binary64, where u = 1.11·10⁻¹⁶. The expression written as it reads has lost half its digits by x = 1.1·10⁻⁸, where its relative error is 0.764, and from x = 1.5·10⁻⁸ down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 3.33·10⁻¹⁶, which is 3.0 unit roundoffs, and the two spellings agree at x = 1 to 5.55·10⁻¹⁷.

cancellation is one function in lib/figures/arith.js — arithmetic — what a float holds, and what it loses holding it. Everything below came out of it during this build, at arguments taken from the essays rather than invented for this page. A figure here is the figure a reader meets in an essay, and if the generator changes, this page changes with it.

At its defaults

Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.

Relative error of two algebraically identical expressions for (1 − cos x)/x², in binary64A log–log plot of relative error against x, in binary64, where u = 1.11·10⁻¹⁶. The expression written as it reads has lost half its digits by x = 1.1·10⁻⁸, where its relative error is 0.764, and from x = 1.5·10⁻⁸ down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 3.33·10⁻¹⁶, which is 3.0 unit roundoffs, and the two spellings agree at x = 1 to 5.55·10⁻¹⁷.10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹xrelative error of the computed value(1 − cos x)/x², as written2 sin²(x/2)/x²no digits left at allbinary64 throughoutone function, two spellings · zero below 1.5·10⁻⁸

A log–log plot of relative error against x, in binary64, where u = 1.11·10⁻¹⁶. The expression written as it reads has lost half its digits by x = 1.1·10⁻⁸, where its relative error is 0.764, and from x = 1.5·10⁻⁸ down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 3.33·10⁻¹⁶, which is 3.0 unit roundoffs, and the two spellings agree at x = 1 to 5.55·10⁻¹⁷.

bits: 53

The arguments are the ones A nearest point that is not there passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

Relative error of two algebraically identical expressions for (1 − cos x)/x², in binary64A log–log plot of relative error against x, in binary64, where u = 1.11·10⁻¹⁶. The expression written as it reads has lost half its digits by x = 1.1·10⁻⁸, where its relative error is 0.764, and from x = 1.5·10⁻⁸ down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 3.33·10⁻¹⁶, which is 3.0 unit roundoffs, and the two spellings agree at x = 1 to 5.55·10⁻¹⁷.10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹xrelative error of the computed value(1 − cos x)/x², as written2 sin²(x/2)/x²no digits left at allbinary64 throughoutone function, two spellings · zero below 1.5·10⁻⁸

A log–log plot of relative error against x, in binary64, where u = 1.11·10⁻¹⁶. The expression written as it reads has lost half its digits by x = 1.1·10⁻⁸, where its relative error is 0.764, and from x = 1.5·10⁻⁸ down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 3.33·10⁻¹⁶, which is 3.0 unit roundoffs, and the two spellings agree at x = 1 to 5.55·10⁻¹⁷.

bits: 24

The arguments are the ones A norm that overflows before it is a norm passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

Relative error of two algebraically identical expressions for (1 − cos x)/x², in binary32A log–log plot of relative error against x, in binary32, where u = 5.96·10⁻⁸. The expression written as it reads has lost half its digits by x = 2.4·10⁻⁴, where its relative error is 0.889, and from x = 3.5·10⁻⁴ down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 1.77·10⁻⁷, which is 3.0 unit roundoffs, and the two spellings agree at x = 1 to 0.10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻⁹10⁻⁶10⁻³1xrelative error of the computed value(1 − cos x)/x², as written2 sin²(x/2)/x²no digits left at allbinary32 throughoutone function, two spellings · zero below 3.5·10⁻⁴

A log–log plot of relative error against x, in binary32, where u = 5.96·10⁻⁸. The expression written as it reads has lost half its digits by x = 2.4·10⁻⁴, where its relative error is 0.889, and from x = 3.5·10⁻⁴ down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 1.77·10⁻⁷, which is 3.0 unit roundoffs, and the two spellings agree at x = 1 to 0.

bits: 16

The arguments are the ones Cancellation takes the answer, not a digit passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

Relative error of two algebraically identical expressions for (1 − cos x)/x², in 16-bitA log–log plot of relative error against x, in 16-bit, where u = 1.53·10⁻⁵. The expression written as it reads has lost half its digits by x = 0.0039, where its relative error is 0.853, and from x = 0.0055 down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 3.45·10⁻⁵, which is 2.3 unit roundoffs, and the two spellings agree at x = 1 to 7.63·10⁻⁶.10⁻⁷10⁻⁵10⁻³10⁻¹10⁻⁶10⁻³1xrelative error of the computed value(1 − cos x)/x², as written2 sin²(x/2)/x²no digits left at all16-bit throughoutone function, two spellings · zero below 0.0055

A log–log plot of relative error against x, in 16-bit, where u = 1.53·10⁻⁵. The expression written as it reads has lost half its digits by x = 0.0039, where its relative error is 0.853, and from x = 0.0055 down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 3.45·10⁻⁵, which is 2.3 unit roundoffs, and the two spellings agree at x = 1 to 7.63·10⁻⁶.

bits: 32

The arguments are the ones Cancellation takes the answer, not a digit passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

Relative error of two algebraically identical expressions for (1 − cos x)/x², in 32-bitA log–log plot of relative error against x, in 32-bit, where u = 2.33·10⁻¹⁰. The expression written as it reads has lost half its digits by x = 1.5·10⁻⁵, where its relative error is 0.854, and from x = 2.2·10⁻⁵ down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 6.75·10⁻¹⁰, which is 2.9 unit roundoffs, and the two spellings agree at x = 1 to 0.10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹xrelative error of the computed value(1 − cos x)/x², as written2 sin²(x/2)/x²no digits left at all32-bit throughoutone function, two spellings · zero below 2.2·10⁻⁵

A log–log plot of relative error against x, in 32-bit, where u = 2.33·10⁻¹⁰. The expression written as it reads has lost half its digits by x = 1.5·10⁻⁵, where its relative error is 0.854, and from x = 2.2·10⁻⁵ down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 6.75·10⁻¹⁰, which is 2.9 unit roundoffs, and the two spellings agree at x = 1 to 0.

bits: 40

The arguments are the ones Cancellation takes the answer, not a digit passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

Relative error of two algebraically identical expressions for (1 − cos x)/x², in 40-bitA log–log plot of relative error against x, in 40-bit, where u = 9.09·10⁻¹³. The expression written as it reads has lost half its digits by x = 9.5·10⁻⁷, where its relative error is 0.819, and from x = 1.3·10⁻⁶ down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 2.3·10⁻¹², which is 2.5 unit roundoffs, and the two spellings agree at x = 1 to 4.55·10⁻¹³.10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹xrelative error of the computed value(1 − cos x)/x², as written2 sin²(x/2)/x²no digits left at all40-bit throughoutone function, two spellings · zero below 1.3·10⁻⁶

A log–log plot of relative error against x, in 40-bit, where u = 9.09·10⁻¹³. The expression written as it reads has lost half its digits by x = 9.5·10⁻⁷, where its relative error is 0.819, and from x = 1.3·10⁻⁶ down it returns exactly zero — every operation correctly rounded and the answer wrong by a factor of infinity. The rearranged form's worst error anywhere on the axis is 2.3·10⁻¹², which is 2.5 unit roundoffs, and the two spellings agree at x = 1 to 4.55·10⁻¹³.

What it checked while drawing

Every figure above checked its own claims on the way to being drawn, and a claim that failed would have stopped the picture rather than shipped a wrong one. Those checks used to leave no trace at all: a passing one returned true and the only evidence the figure had checked anything was that nothing crashed. The list below is what they actually said, collected by running this generator with an observer installed — not a description of what it is believed to check.

13 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.

and from x = 0.0055 down it returns exactly zero

and from x = 1.3·10⁻⁶ down it returns exactly zero

and from x = 1.5·10⁻⁸ down it returns exactly zero

and from x = 2.2·10⁻⁵ down it returns exactly zero

and from x = 3.5·10⁻⁴ down it returns exactly zero

the naive form has lost half its digits by x = 0.0039

the naive form has lost half its digits by x = 1.1·10⁻⁸

the naive form has lost half its digits by x = 1.5·10⁻⁵

the naive form has lost half its digits by x = 2.4·10⁻⁴

the naive form has lost half its digits by x = 9.5·10⁻⁷

the stable-form tolerance sits between the measured noise floor and the smallest real failure

the two spellings agree where nothing cancels

while the stable form holds to rounding level throughout

Against the rule

The rule does not apply to it. It factorises nothing, so there is no residual it could be withholding. That is worth stating rather than leaving blank: a site that reported the rule as satisfied by every generator would be counting mostly generators the rule never reached.

Across the library: the rule bites on 217 of 397 generators — 199 print a residual and 18 are exempt with a published reason; 180 factorise nothing. Read from lib/residual-rule.js, which is the same body the gate enforces from, and the gate's last check fails the build if this page and it disagree about any generator.

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

When the index is a tuple

A nearest point that is not there

Eckart and Young guarantee that a matrix has a best rank-k approximation and that the truncated SVD is it. For three indices the guarantee is false in the strongest available way — there are tensors whose distance to the rank-two set is zero and which no rank-two tensor equals.

 The arithmetic underneath

A norm that overflows before it is a norm

The vector of sixteen thousands has a Euclidean norm of 4,000, which fp16 represents exactly. Written as the square root of the sum of squares it returns infinity, because squaring doubles the exponent — and the expression costs half the format's range on the one computation every iterative method performs at every step.

 The arithmetic underneath

Buying the accuracy back

Factorise in single precision, then correct the answer using residuals computed in double, and the result is what a full double-precision solve would have given. Compute those residuals in single instead and the identical algorithm, at identical cost, recovers nothing.

 The arithmetic underneath

Cancellation takes the answer, not a digit

Subtracting two nearly equal numbers is exact. That is what makes it dangerous — the subtraction introduces no error at all, it exposes error the operands were already carrying, and the exposure can consume every significant figure at once.

 Eigenvalues, singular values, rank

The series that has to be squared back

The Taylor series for the matrix exponential is not wrong — every term is computed correctly — and on Moler and Van Loan's two-by-two its largest term is 5.4 million times the answer it sums to. The method that replaces it scales the matrix down and squares the result back, and both halves of that sentence cost: too few squarings and the approximant is out of range, too many and each one doubles the rounding.

The whole library · All essays · What must fail