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

From Drewiki
Jump to: navigation, search

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
Personal tools