Consider the following pseudo-code fragment, where 𝑎 and 𝑏 are integer…

Concept: When a loop repeatedly multiplies an accumulator by a constant factor a (with a > 1) until it first reaches or exceeds a threshold b, the number of multiplications needed is the smallest integer k such that ak ≥ b. By the definition of the ceiling function, that smallest k equals ⌈loga b⌉ — the discrete analogue of exponential growth crossing a fixed threshold.

Applying it to this loop:

1. Before the loop, x = 0 and p = 1.

2. Loop invariant: immediately before each condition check, p = ax (x completed multiplications so far).

3. The body (p = p·a; x = x + 1) runs once more each time p < b, so p climbs through the powers a, a2, a3, … as x increases.

4. The loop stops the very first time p ≥ b — that is, at the smallest x with ax ≥ b, which by the concept above is x = ⌈loga b⌉.

Cross-check: take a = 2, b = 10. p takes the values 2, 4, 8, 16 after x = 1, 2, 3, 4 multiplications; p first reaches/exceeds 10 at x = 4, and ⌈log2 10⌉ = ⌈3.32⌉ = 4 — matching. Equivalently, at termination ax-1 < b ≤ ax (the powers of a strictly increase since a > 1, the given pre-condition), which is exactly the defining property of x = ⌈loga b⌉.