SICP exercise 1.46

From Drewiki

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.

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.

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

Output:

3.00009155413138

Output:

10.0000000001399

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.

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

Tests:

Output:

3.0

Output:

4.00000000000005

Output:

8.00000000000017

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

Output:

1.99999818247885

Output:

2.99999723210577

Output:

6.99999750595221