C.29.2:5.2 - Turn a root condition into a bounded approximation

Question and representation. Return a rational approximation y to the positive root of z^2 = 2 with |y - sqrt(2)| <= 0.001. The equation characterizes the root. The requested rational output still needs a way to compute it. Use exact rational arithmetic in this construction.

The initial interval is [l,u] = [1,2] because 1^2 <= 2 <= 2^2. For nonnegative arguments squaring is increasing, so a comparison of the midpoint’s square with 2 determines which half still contains the root.

l := 1
u := 2
epsilon := 1/1000
while u - l > 2*epsilon:
    m := (l + u)/2
    if m*m < 2:
        l := m
    else:
        u := m
return (l + u)/2

Meaning and argument. The preserved statement is 1 <= l <= sqrt(2) <= u <= 2. The square comparison preserves it, and every iteration halves the interval width. After k iterations that width is 2^(-k). The returned midpoint therefore differs from the root by at most 2^(-k-1). Choosing the first k for which this is at most epsilon supplies both the stopping rule and a finite bound on the iteration count for every positive requested tolerance.

After nine halvings, return 1449/1024 = 1.4150390625. Its error is at most 1/1024 = 0.0009765625, which satisfies the requirement. The interval argument establishes the bound without requiring a previously calculated decimal expansion of the root.

Resource and accuracy consequences. There are nine midpoint-square comparisons in this case. For finer tolerances, the dyadic numerators and denominators grow; a count of comparisons alone does not include the growing cost of exact squaring. A finite precision version must preserve the bracket decisions and avoid a midpoint that rounds to an endpoint while the tolerance remains unmet. Output rounding also consumes accuracy. These are returns to arithmetic and representation choices, not evidence that the exact rational construction failed.

For a costly general continuous function, an established bracketed method using interpolation may save function evaluations. Bisection remains useful when a simple interval argument and predictable reduction are worth the extra evaluations. For a function not known to be continuous, a sign change alone does not justify this root argument. A demand for an exact finite decimal expansion of this irrational root changes the answer format to an impossible one; an exact symbolic expression or a rational approximation is a different, obtainable request.