11  Testing and Validating Computations

11.1 Learning objectives

After completing this unit, you will be able to:

  • use assertions to state results or invariants that can be checked;
  • distinguish example-based testing from property-based testing;
  • distinguish unit, integration, and regression tests;
  • choose an oracle without copying the algorithm under test;
  • use exact equality and numerical tolerances where each is appropriate;
  • test boundary values, preconditions, and error behavior;
  • formulate metamorphic relations and invariants;
  • validate an implementation against independently derived results; and
  • limit claims based on testing so they are not mistaken for general mathematical proofs.

Local prerequisites: Units 1–5, functions, finite sums, quadratic equations, and the concept of a domain. This unit requires only the Python standard library.

11.2 Assertions and contracts

An assertion states a condition expected to hold at a particular point in execution. In unittest tests, expressions such as self.assertEqual(actual, expected) record a failure as a test result. Python’s built-in assert statement is better suited to internal invariants whose failure indicates a programming error.

Listing 11.1 
def triangular_iterative(n):
    if isinstance(n, bool) or not isinstance(n, int):
        raise TypeError("n must be an integer")
    if n < 0:
        raise ValueError("n must be nonnegative")

    total = 0
    for k in range(1, n + 1):
        previous = total
        total += k
        assert total >= previous
    return total

Do not use assert n >= 0 as the sole validation of public input. Python can remove assert statements when run with optimization enabled. Preconditions on user input must be checked explicitly and produce documented error types.

11.3 Examples and properties

An example test pairs a particular input with a known output:

nn 1+2+⋯+n1+2+\cdots+n
0 0
1 1
2 3
10 55
100 5,050

Examples are easy to read and especially useful for important cases or previously discovered errors. A few examples, however, do not explain the structure of the entire domain.

A property test checks a relation that should hold for many inputs. If T(n)=1+2+⋯+nT(n)=1+2+\cdots+n, then

T(n+1)−T(n)=n+1 T(n+1)-T(n)=n+1

and

T(2n)=2T(n)+n2. T(2n)=2T(n)+n^2.

The second relation does not determine one output from scratch; it relates several function calls. Such a relation is called metamorphic and is useful when the correct output for each input is difficult to calculate directly.

Testing a property at a thousand fixed values is still a finite check. It covers more ground than five examples, but it is not a universal proof.

11.4 Unit, integration, and regression tests

These three labels answer different questions.

Level Focus Unit 8 example
unit one function or small contract triangular_iterative(10) == 55
integration several parts working together the oracle, properties, and JSON writer produce a valid report
regression a particular error does not recur the boundary value n=0 still produces 0

A regression test is usually added after an error has been found and fixed. It should preserve the smallest input that triggers the error and the correct result. Calling every large test a “regression” obscures the failure history that the test is actually intended to guard against.

11.5 Oracles and reference values

An oracle is a source for deciding what the correct output is. Options include:

  • small values calculated and reviewed in advance;
  • a mathematical definition or identity;
  • a simpler reference implementation;
  • reference data with clearly documented origins; or
  • invariants and metamorphic relations.

An oracle that repeats production code under a different name is not independent. The same error can exist in both places while every test passes.

The implementation tested in this unit adds the integers from 1 to n in a loop. Its main oracle is derived by pairing terms. Write the sum in forward and reverse order:

T(n)=1+2+⋯+n, T(n)=1+2+\cdots+n,

T(n)=n+(n−1)+⋯+1. T(n)=n+(n-1)+\cdots+1.

Adding the two lines gives nn pairs, each with value n+1n+1. Thus

2T(n)=n(n+1),T(n)=n(n+1)2. 2T(n)=n(n+1), \qquad T(n)=\frac{n(n+1)}{2}.

The reference function uses this formula, not a second loop. Agreement between the two is therefore more informative than a comparison of two copies of the same loop.

11.6 Exact equality and tolerances

If the result is an exact integer or rational number, use exact equality. triangular_iterative(10) must equal 55, not merely be close to it. A tolerance in such a test can hide an off-by-one error.

For a floating-point approximation, specify the quantity being checked and justify its tolerance. Newton iteration for x2=2x^2=2 produces an approximation to the square root of two. The Unit 8 test checks the residual

|x2−2|≤10−12 |x^2-2|\le 10^{-12}

after five iterations starting from x0=1x_0=1.

from math import isclose

x = 1.0
for _ in range(5):
    x = 0.5 * (x + 2.0 / x)

isclose(x*x, 2.0, rel_tol=0.0, abs_tol=1e-12)
Listing 11.2 
True

The tolerance is applied to a residual with a clear meaning. Do not choose a tolerance after seeing a failure merely to make the test turn green.

11.7 Boundary values and domains

The summation function in this unit has the nonnegative integers as its domain. Tests should check at least:

  • the boundary n=0;
  • the first positive value n=1;
  • an ordinary value such as n=10;
  • negative values, which must be rejected;
  • noninteger numbers, which must be rejected; and
  • True, because bool is a subclass of int in Python but is not an input intended by this mathematical contract.

Error tests need to check the type of failure, not merely that “something failed.” A ValueError for a negative integer and a TypeError for 2.5 express two different contract violations.

11.8 Invariants and metamorphic testing

A simple loop invariant is that the sum does not decrease after the next positive integer is added. Metamorphic relations compare different calls:

Listing 11.3 
for n in range(201):
    value = triangular_iterative(n)
    assert triangular_iterative(n + 1) - value == n + 1
    assert triangular_iterative(2*n) == 2*value + n*n

Metamorphic relations do not require a table of 201 answers, but they still require a derivation. For the doubling relation,

T(2n)−2T(n)=n(2n+1)−n(n+1)=n2. T(2n)-2T(n) =n(2n+1)-n(n+1) =n^2.

If a relation is formulated incorrectly, the test can reject a correct implementation. Test code needs review just as production code does.

11.9 Independent validation

Validation asks whether the program answers the intended question, not merely whether it is consistent with itself. In this unit:

  1. the specification defines T(n)T(n) as the sum of the integers from 1 to nn;
  2. the implementation uses repeated addition;
  3. the oracle uses the independently derived pairing formula;
  4. the table of small values provides an easily checked reference point; and
  5. the increment and doubling properties provide additional cross-checks.

These different layers reduce the risk of a single error passing unnoticed. They do not make validation perfect: the specification may be wrong, the oracle may have been derived incorrectly, or the test domain may miss a defect.

11.10 A deterministic report

Run from the project root:

python source/code/unit08_validation.py

The report contains reference values, comparisons with the pairing formula, property violations, boundary and domain checks, numerical residuals, test levels, and limits on the conclusions. The JSON uses UTF-8, sorted keys, fixed indentation, and LF line endings. core_sha256 binds the core contents before the hash field is added. This execution path uses no current time, network access, or random numbers.

Two byte-identical outputs show that two executions recorded the same results under the same conditions. This does not establish that the oracle or specification is necessarily correct.

11.11 Coverage, evidence, and proof

Coverage has several meanings. Line coverage says which parts of the code were executed. Branch coverage says which control-flow alternatives were taken. Domain coverage says which mathematical inputs were checked. Having 100% line coverage does not mean that every value or property has been tested.

If the program agrees with the pairing formula for 0 <= n <= 1000, the justified conclusion is that no mismatch was found on that finite domain in the execution environment used. The proof of the pairing formula applies to all nonnegative integers because it treats nn generally and pairs the terms. A proof that the loop implements the sum can use a loop invariant. Tests support the claim that the concrete implementation agrees with the argument in the cases checked; tests alone do not replace either proof.

11.12 Exercises

11.12.1 Exercise 1 — choosing an assertion

For each of the following claims, choose exact equality or a comparison with a tolerance and explain your choice: (a) the sum 1+...+100, (b) a numerical approximation to 2\sqrt{2}, and (c) the length of an output list.

Ask whether the representation and the specified result are exact.

Use exact equality for (a), namely 5050, because Python integer operations in this range are exact. Use a comparison with a tolerance for (b), deriving the tolerance from a residual or the requirements of the problem. Use exact equality for (c), because a list length is an integer. A tolerance for the length could accept a list with the wrong number of elements.

11.12.2 Exercise 2 — constructing an oracle

You are testing a function that calculates 1+3+5+⋯+(2n−1)1+3+5+\cdots+(2n-1) with a loop. Derive an oracle that does not use the same loop and state its domain.

Draw a square that gains one L-shaped border at each step.

The sum of the first nn odd numbers is n2n^2. A square of size (n−1)×(n−1)(n-1)\times(n-1) gains 2n−12n-1 new points to become an n×nn\times n square. The oracle can therefore calculate n*n for a nonnegative integer n. Compare the loop implementation with that formula, not with a copy of the loop.

11.12.3 Exercise 3 — metamorphic relations

For the function S(n)=n2S(n)=n^2, write two metamorphic relations that can be tested without a complete table of values. Explain why the relations are valid.

Compare S(n+1)S(n+1) with S(n)S(n), then try the input −n-n.

Two relations are S(n+1)−S(n)=2n+1S(n+1)-S(n)=2n+1 and S(−n)=S(n)S(-n)=S(n). The first follows from (n+1)2−n2=2n+1(n+1)^2-n^2=2n+1; the second follows from (−n)2=n2(-n)^2=n^2. They can detect different classes of error, but boundary examples and direct checks against some reference values are still needed.

11.12.4 Exercise 4 — a boundary regression test

A mean function once divided by zero when given an empty list, although its contract required it to reject that input with ValueError. Write the core of its regression test and explain why the test should be retained.

Use with self.assertRaises(ValueError):.

The core is with self.assertRaises(ValueError): mean([]). Retain the test because it preserves the smallest input that once violated the contract and the behavior now required. If a later refactor returns NaN or allows ZeroDivisionError to escape, the test shows that the public behavior has changed.

11.12.5 Exercise 5 — the limits of testing evidence

All tests pass, every line of code is covered, and a million random inputs reveal no failure. State the strongest justified conclusion and give two reasons why this is not yet a general proof.

Distinguish execution coverage from domain coverage, and examine the oracle.

The strongest conclusion is that the implementation passed the stated tests, coverage checks, and samples in that environment. This is not a general proof because a million samples do not exhaust an infinite domain, and the oracle or specification may share errors with the implementation. A general proof requires an argument covering the entire domain; further validation requires independent oracles, boundary cases, properties, and environment records.

11.13 Summary

  • Appropriate assertions state local contracts that can be checked.
  • Examples cover important cases; properties and metamorphic relations extend the checks without automatically providing a universal proof.
  • Unit, integration, and regression tests protect against different layers of risk.
  • Oracles must come from values, derivations, data, or implementations sufficiently independent of the code under test.
  • Exact equality suits exact results; tolerances must reflect numerical meaning and scale.
  • Boundary values, invalid domains, and error types are part of the contract.
  • Cross-validation and canonical reports strengthen the evidence.
  • Coverage and passing tests do not replace general mathematical proof.