C / LOOPS AND JUMPS
while loops and proving they terminate
Write while loops in C and back each one with a termination argument: name the quantity that strictly decreases and the bound where the condition fails.
What you will learn
- Read while as test-first: a condition false on arrival gives zero passes.
- Name a loop variant: a bounded integer the body drives strictly downward each pass.
- Spot conditions that can never turn false: unsigned >= 0, float !=, untouched state.
- Know that an accidental non-terminating loop is undefined behaviour in C, not just slow.
Understanding while loops and proving they terminate
`while (cond) body` evaluates cond before every pass and runs body only while cond is nonzero, so a condition that is already false gives zero passes. C gives you no automatic advance the way a for header suggests one; the loop moves only because the body writes to something the condition reads. That is the first thing to check when a while loop hangs: list the variables the condition reads, then find where the body changes them.
A termination argument is short and mechanical. Pick a variant: an integer expression over the condition's variables, bounded below, that the body drives strictly downward by at least one on every path through it. A non-negative integer cannot fall forever, so the loop must reach a value at which the condition is false. For `while (n > 0) n /= 2;` the variant is n itself, bounded below by 0, made strictly smaller by integer division for every n > 0, and rejected by the test at n == 0 — that is the whole proof, and it also tells you the pass count is about log2(n).
Proofs break in a few recognisable ways. The measure may not fall on every path through the body, the type may have no room below the bound (an unsigned counter wraps from 0 to UINT_MAX instead of going negative), or the step may shrink toward nothing, as with floating point and `!=` tests. Loops driven by input replace the numeric argument with a claim about the stream — `while (scanf("%d", &v) == 1)` ends because a file eventually stops yielding integers — which is why an unchecked EOF turns a read loop into a spin. And when you cannot name a variant at all you have no proof: nobody can supply one for `while (n != 1) n = (n % 2) ? 3 * n + 1 : n / 2;`, which is exactly why the Collatz question is still open.
placeholder
<stdio.h>
int main(void)
{
unsigned int n = 1000;
unsigned int start = n;
int digits = 0;
/* Variant: n. It is a non-negative integer, the body replaces it by
n / 2 which is strictly smaller for every n > 0, and the condition
is false at the floor n == 0. So this loop cannot run forever. */
while (n > 0) {
printf("n = %4u digits so far = %d\n", n, digits);
n /= 2;
digits++;
}
printf("%u needs %d binary digits\n", start, digits);
return 0;
}
A while loop is provably finite exactly when its body drives some bounded, strictly decreasing measure toward a value the condition rejects.
Worked examples
An unsigned countdown has no floor to hit
Shows why `i >= 0` is not a termination test when i is unsigned, and what the decrement does at zero.
<stdio.h>
<limits.h>
int main(void)
{
unsigned int i = 2;
int passes = 0;
/* "i >= 0" is true for every unsigned value, so it tests nothing.
Only the passes guard ends this loop. */
while (i >= 0 && passes < 3) {
printf("pass %d: i = %u\n", passes, i);
i--;
passes++;
}
printf("after the pass at i == 0, i == UINT_MAX: %d\n", i == UINT_MAX);
return 0;
}
Example explained
Line 1`i >= 0` compares an unsigned value with 0, so it is a constant true; compiling with -Wextra reports that the comparison is always true.
Line 2The third pass runs with i == 0, and `i--` then wraps to UINT_MAX, because unsigned arithmetic is modular rather than an error.
Line 3Without `passes < 3` the loop never ends: from UINT_MAX it counts back down to 0 and wraps again, forever.
Line 4The provable form uses a bound the value can reach: `while (i > 0)` with the body indexing `a[i - 1]` and then decrementing.
A floating point equality test that never becomes false
Shows a variant that decreases but never lands on the value the condition compares against.
<stdio.h>
int main(void)
{
double x = 1.0;
int steps = 0;
/* x != 0.0 never becomes false: 0.1 is not exactly representable,
so x drifts off the decimal grid. The steps guard stops us. */
while (x != 0.0 && steps < 10) {
x -= 0.1;
steps++;
}
printf("steps = %d\n", steps);
printf("x = %.17g\n", x);
printf("x > 0.0: %d\n", x > 0.0);
return 0;
}
Example explained
Line 1`x -= 0.1` subtracts the double nearest 0.1, which is slightly larger than one tenth, and each subtraction rounds the result again.
Line 2After ten passes the leftover is 5 x 2^-55, printed as 1.3877787807814457e-16, so `x != 0.0` is still true.
Line 3Drop the `steps < 10` guard and the loop runs forever: x keeps stepping down through negative values and never equals 0.0 exactly.
Line 4Testing `x > 0.0` instead is provable, since each pass lowers x by about 0.1 and it crosses zero on the eleventh pass.
Important notes
C deliberately permits `while (1)` to spin forever; the rule that lets a compiler assume termination applies only when the controlling expression is not a constant and the body performs no I/O, volatile access or synchronisation.
A variant proves the loop ends, not that it ends soon: `n /= 2` gives about log2(n) passes and `n -= 1` gives n, yet both proofs have the same shape.
Common mistakes
Testing one variable and updating another, as in `while (i < n)` with `j++` in the body: the condition never changes, and since the body does no I/O the compiler is allowed to assume the loop ends, so the symptom can be a deleted loop or garbled control flow rather than a clean hang.
Counting down with an `unsigned` index and testing `i >= 0`: the test is true for every value, so at 0 the decrement wraps to UINT_MAX and the loop restarts its descent instead of finishing.
Writing `while ((c = getchar()) != '\n')` and ignoring end of file: on input with no final newline getchar keeps returning EOF and the loop spins, so the test needs `c != '\n' && c != EOF`.
Try it yourself
Change, predict, then run
Write a while loop that adds up the decimal digits of 90210 using `n % 10` and `n /= 10`, with a comment above it naming the variant, its step and its bound. Then set n to -90210 and say what the variant has to become for the argument to still hold.
Open the C workspaceCheck your understanding
A binary search loop reads: `int lo = 0, hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < key) lo = mid + 1; else hi = mid; }`. Which fact proves the loop terminates?
- The array is sorted, so key is located before the indices meet.
- `hi - lo` is a non-negative integer that gets strictly smaller on every pass.
- `lo` only ever grows, so it must eventually pass `hi`.
- `mid` is recomputed each pass, so it can never repeat a value.
Show answer
`hi - lo` starts at n and shrinks on both branches: `lo = mid + 1` puts lo above mid, which is at least lo, and `hi = mid` puts hi below the old hi because (hi - lo) / 2 < hi - lo whenever lo < hi. A non-negative integer that drops by at least one each pass must reach 0, where `lo < hi` is false. The answer about lo growing is tempting since lo really is non-decreasing, but a run of passes can take the else branch and never touch lo, so lo alone bounds nothing; the measure has to fall on every path. Sortedness is about getting the right answer, not about stopping.