## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.46

## Problem

Several of the numerical methods described in chapter 1 of the text 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 in the text and the `fixed-point` procedure of section 1.3.3 in terms
of `iterative-improve`.

## Solution

Here's one implementation of the requested `iterative-improve`
procedure. Note that some iterative improvement algorithms will
need to compare the current guess to the next guess in order to tell
when the next guess is good enough, and others will only need the
current guess. To accomodate both approaches, the `good-enough?`
argument is a procedure which takes two arguments, the first of which
is the current guess and the 2nd the next guess. Procedures which
use `iterative-improve` can choose to ignore either argument in their
`good-enough?` implementations.

(define (iterative-improve good-enough? improve) (define (check guess) (let ((next-guess (improve guess))) (if (good-enough? guess next-guess) next-guess (check next-guess)))) (lambda (initial-guess) (check initial-guess)))

Here's an implementation of the `sqrt` method from section 1.1.7 which
uses `iterative-improve`. Its `good-enough?` test ignores the `guess`
argument and uses only `next-guess`.

(define (average x y) (/ (+ x y) 2)) (define (square x) (* x x)) (define (sqrt x) (define (good-enough? guess next-guess) (< (abs (- (square next-guess) x)) 0.001)) (define (improve guess) (average guess (/ x guess))) ((iterative-improve good-enough? improve) x))

Tests (results from Chicken Scheme 3.1 on a MacBook Pro running Mac OS X 10.5):

(sqrt 9)

*Output:*

`
`

3.00009155413138

(sqrt 100)

*Output:*

`
`

10.0000000001399

(sqrt 64)

*Output:*

`
`

8.00000165528959

And here's a fixed-point procedure from section 1.3.3 which uses
`iterative-improve`: its `close-enough?` test uses both arguments.

(define tolerance 0.00001) (define (fixed-point f first-guess) (define (close-enough? guess next-guess) (< (abs (- guess next-guess)) tolerance)) (define (improve guess) (f guess)) ((iterative-improve close-enough? improve) first-guess))

Here are a few tests using this `fixed-point` procedure, including
another `sqrt` implementation using average damping.

(define (average-damp f) (lambda (x) (average x (f x)))) (define (fixed-point-sqrt x) (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))

Tests:

(fixed-point-sqrt 9)

*Output:*

`
`

3.0

(fixed-point-sqrt 16)

*Output:*

`
`

4.00000000000005

(fixed-point-sqrt 64)

*Output:*

`
`

8.00000000000017

And just for good measure, here's a `cube-root` procedure:

(define (cube-root x) (fixed-point (average-damp (lambda (y) (/ x (square y)))) 1.0))

(cube-root 8)

*Output:*

`
`

1.99999818247885

(cube-root 27)

*Output:*

`
`

2.99999723210577

(cube-root (* 7 7 7))

*Output:*

`
`

6.99999750595221