Exercise 1.46: Several of the numerical methods described in this chapter are instances of
an extremely general computational strategy known as iterative improvement. Iterative improvement
says that, to compute something, we start with an initial guess for the answer, test if the guess
is good enough, and otherwise improve the guess and continue the process using the improved
guess as the new guess. Write a procedure iterative-improve that takes two procedures as
arguments: a method for telling whether a guess is good enough and a method for improving a
guess. Iterative-improve should return as its value a procedure that takes a guess as argument
and keeps improving the guess until it is good enough. Rewrite the sqrt procedure of section
1.1.7 and the fixed-point procedure of section 1.3.3 in terms of iterative-improve. The
first two functions were written in the form of earlier exercises. The -iter functions are
implemented with iterative-improve.
(define (sqrt guess x)
(define (improve guess x)
(define (average a b) (/ (+ a b) 2))
(average guess (/ x guess)))
(define (great-enough? oldguess guess)
(< (abs (- 1 (/ oldguess guess))) 0.0001))
(if (great-enough? guess (improve guess x))
(improve guess x)
(sqrt (improve guess x)
x)))
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(define (iterative-improve close-enough? improve)
(define (iter guess)
(let ((new-guess (improve guess)))
(if (close-enough? guess new-guess)
new-guess
(iter new-guess))))
iter)
(define (sqrt-iter x)
(define (improve guess)
(define (average a b) (/ (+ a b) 2))
(average guess (/ x guess)))
(define (great-enough? oldguess guess)
(< (abs (- 1 (/ oldguess guess))) 0.0001))
((iterative-improve
great-enough?
improve)
1.0))
(define (fixed-point-iter f)
(define tolerance 0.0001)
(define (close-enough? v1 v2)
(< (abs (- 1 (/ v1 v2))) tolerance))
(define (improve guess) (f guess))
((iterative-improve
close-enough?
improve)
1.0))
Old implementations:
> (sqrt 1.0 2)
1.4142135623746899
> (fixed-point (lambda (y) (* 0.5 (+ (/ 2 y) y))) 1.0)
1.4142135623746899
New implementations:
> (fixed-point-iter (lambda (y) (* 0.5 (+ (/ 2 y) y))))
1.4142135623746899
> (sqrt-iter 2)
1.4142135623746899