Repeated refinement turns a guess into an approximation.
A square-root process can repeatedly average a guess with the quotient of the target and that guess, making the squared estimate approach the target.
How does one local improvement rule create an increasingly accurate numerical process?
- Read a guess as the complete state of one iteration
- Apply Newton-style square-root improvement
- Compare an estimate with its squared value
- Separate a fixed observed run from a convergence claim
If guess is too large, x divided by guess is too small, and conversely. Averaging those two values produces the next guess between them. The process carries only that new guess into the next call.
These programs use a fixed refinement count rather than a hidden tolerance. Six steps from 1.0 give a deterministic observation for √2, while the explicit history shows how the change between guesses rapidly shrinks.
(begin
(define (average left right) (/ (+ left right) 2.0))
(define (improve guess x) (average guess (/ x guess)))
(define (refine guess x remaining)
(if (= remaining 0)
guess
(refine (improve guess x) x (- remaining 1))))
(let ((estimate (refine 1.0 2.0 6)))
(list estimate (* estimate estimate))))- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns (1.414213562373095 1.9999999999999996). The second records five guesses from 1.0 through 1.4142135623746899.
Follow each refine call and locate the quotient, average, and remaining-count update. The fixed count describes this run without claiming convergence for every starting guess or target.
Change the program before you read the hint.
Change the target to 9.0 and keep six refinements from 1.0. Predict the estimate and its square before running.
Show one hint
Apply the same average of guess and x divided by guess. Only the target changes.