Each worksheet prints cleanly on A4 or Letter. Answer keys are on a separate page.

The Lumenary · First-year graduate

Computational reproducibility

Name: ______________________

Date: ______________________

You will learn to

Package a computation with version control, a pinned environment, tests and a single command that regenerates its results
Classify a computational claim as exact, numerical, statistical or experimental, and state what it does not establish
Prove the standard error bound for floating-point summation and use it to choose and justify tolerances
Turn numerical results into theorems with interval arithmetic, and make results checkable with certificates
Archive code and data with persistent identifiers and cite software properly

1.
Which of these reports state their evidence honestly? (Choose all that apply.)
- A."With seed 7, NumPy 1.26.4 and $10^6$ samples, our Monte Carlo estimate is $0.7466 \pm 0.0011$ (95% confidence interval)."
- B."We checked the conjecture for all $n \le 10^9$ ; it is therefore true."
- C."Interval arithmetic with outward rounding shows $1.41421356 \lt \sqrt 2 \lt 1.41421357$ ."
- D."Our formula agrees with the computed value to 15 digits, which proves it."
- E."Summed in double precision; the result is exact because floating point is deterministic."
2.
In IEEE double precision ( $p = 53$ ), let x = 1e16. What does (x + 1) - x evaluate to?
3.
In double precision, 1 - math.cos(1e-8) evaluates to 0.0, although $1 - \cos(10^{-8}) \approx 5 \times 10^{-17}$ . Which explanation is correct?
- A.math.cos(1e-8) is correctly rounded to 1.0, because doubles next to $1$ are about $10^{-16}$ apart; the subtraction is then exact and reveals that earlier rounding.
- B.Subtracting two nearly equal numbers is itself an inaccurate floating-point operation.
- C.The library's cosine function has a bug.
- D.No floating-point formula can compute this quantity accurately.
4.
Theorem 2 bounds the error of recursive summation by $\gamma_n \sum |x_i|$ , not by $\gamma_n |\sum x_i|$ . Why can the bound not be improved to a multiple of $|\sum x_i|$ ?
- A.Because of cancellation: the exact sum can be $0$ while the partial sums, and hence the rounding errors, are large.
- B.Because absolute values make the proof easier, but the stronger bound is also true.
- C.Because the bound must also hold for complex numbers.
- D.Because the rounding errors $\delta_k$ might all have the same sign.
5.
Using interval multiplication, compute $[-1, 2] \cdot [-1, 2]$ . What is the lower endpoint of the result?
6.
A program you do not trust outputs: $\gcd(1071, 462) = 21$ , with certificate $x = -3$ , $y = 7$ . What can you conclude?
- A.The claim is proved: $1071\cdot(-3) + 462\cdot 7 = 21$ , and $21$ divides both $1071 = 51 \cdot 21$ and $462 = 22 \cdot 21$ .
- B.Nothing, unless we rerun Euclid's algorithm ourselves.
- C.The certificate is invalid, because Bézout coefficients must be positive.
- D.The certificate only shows that $21$ is a common divisor.
7.
In the Lean module, fsum x δ n is the floating-point recursive sum of x 0, …, x n with rounding errors δ. Which statement correctly formalises Theorem 2?
- A.∀ u, 0 ≤ u → (∀ k, |δ k| ≤ u) → |fsum x δ n - ∑ i ∈ range (n+1), x i| ≤ ((1+u)^n - 1) * ∑ i ∈ range (n+1), |x i|
- B.|fsum x δ n - ∑ i ∈ range (n+1), x i| ≤ ((1+u)^n - 1) * ∑ i ∈ range (n+1), |x i| with no hypothesis on δ
- C.∀ u, 0 ≤ u → (∀ k, |δ k| ≤ u) → |fsum x δ n - ∑ i ∈ range (n+1), x i| ≤ u * |∑ i ∈ range (n+1), x i|
- D.∃ δ, fsum x δ n = ∑ i ∈ range (n+1), x i
8.
You want a colleague to be able to regenerate every figure of your paper in five years' time. Which is the best plan?
- A.A versioned repository with a lock file of exact dependency versions, recorded seeds, tests, one command that rebuilds everything, and a release archived with a DOI.
- B.A requirements.txt saying numpy>=1.20 and the notebook as it was last run.
- C.High-resolution images of all the figures in the supplementary material.
- D.A detailed description of the algorithms in the paper; the code is not needed.
9.
Implement Kahan's compensated summation kahan_sum(xs). Keep a running sum s and a compensation c for the low-order bits lost so far: for each x, set y = x - c, t = s + y, c = (t - s) - y, s = t. The tests compare your result with the exact rational sum.
Computational — Practice

Answer key — Computational reproducibility

1.
(a) and (c). (a) is a statistical claim with its confidence level and everything needed to repeat it. (c) is a rigorous enclosure. (b) and (d) upgrade experimental or numerical evidence to proof, and (e) confuses determinism with exactness.
2.
Between $2^{53} \approx 9.007\times 10^{15}$ and $2^{54}$ the doubles are the even integers. $10^{16} + 1$ is halfway between $10^{16}$ and $10^{16} + 2$ , and round-half-to-even chooses $10^{16}$ (its significand is even). So x + 1 == x and (x + 1) - x is $0$ . The small addend has been absorbed — the reason why summation order matters.
3.
(a). Doubles just below $1$ are spaced $2^{-53} \approx 1.1 \times 10^{-16}$ apart, so the correctly rounded value of $\cos(10^{-8})$ is $1$ . The subtraction $1 - 1$ is exact (Sterbenz). The cure is to avoid forming $\cos x$ at all: $1 - \cos x = 2\sin^2(x/2)$ .
4.
(a). The rounding error committed at step $k$ is $s_k\delta_k$ , proportional to the partial sum, not the final sum. With $x = (1, 10^{-16}, -1)$ the computed result is $0$ , while the exact sum is $10^{-16}$ : a relative error of $100\%$ . The relative error of a sum is governed by the condition number $\sum|x_i|/|\sum x_i|$ .
5.
The products are $1, -2, -2, 4$ , so $[-1,2]\cdot[-1,2] = [-2, 4]$ , and the lower endpoint is $-2$ . This is a valid enclosure of $\{xy : x, y \in [-1, 2]\}$ , but as an enclosure of $\{x^2 : x \in [-1,2]\} = [0, 4]$ it is too wide — the dependency problem. Writing $x^2$ as a single operation (an interval square function) gives the sharp $[0, 4]$ .
6.
(a). $1071 \cdot (-3) + 462 \cdot 7 = -3213 + 3234 = 21$ , and $21 \mid 1071$ , $21 \mid 462$ . Any common divisor of $1071$ and $462$ divides $21$ , and $21$ is itself a common divisor, so it is the gcd. Checking took a few multiplications — far less than trusting the program.
7.
(a). It quantifies over the unit roundoff u, assumes the standard model |δ k| ≤ u for every step, and bounds the error by ((1+u)^n - 1) Σ |xᵢ|. Option (b) drops the hypothesis, (c) claims a false bound, and (d) is vacuous.
8.
(a). Reproduction needs the exact code (version control), the exact environment (lock file or container), the randomness (seeds), the data (with checksums), a single command, and a durable archive (a DOI from a repository such as Zenodo).
9.
```
def kahan_sum(xs):
    s = 0.0
    c = 0.0
    for x in xs:
        y = x - c
        t = s + y
        c = (t - s) - y
        s = t
    return s
```
In exact arithmetic c is always $0$ ; in floating point, (t - s) - y recovers (the negative of) the part of y that was lost when forming t, and the next step adds it back. Kahan's method has error at most $(2u + O(nu^2))\sum|x_i|$ , essentially independent of $n$ , compared with $\gamma_{n-1}\sum|x_i|$ for plain summation. Beware: an optimising compiler that treats floating-point addition as associative would simplify c to $0$ — one reason such reorderings are forbidden by default.