Exercise 1.45 of SICP

2009-07-15

sicp

Exercise 1.45: We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of \( y \mapsto \frac{x}{y} \) does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped \( y \mapsto \frac{x}{y^2} \). Unfortunately, the process does not work for fourth roots – a single average damp is not enough to make a fixed-point search for \( y \mapsto \frac{x}{y^3} \) converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of \( y \mapsto \frac{x}{y^3} \) ) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute nth roots as a fixed-point search based upon repeated average damping of \( y \mapsto \frac{x}{y^{n-1}} \). Use this to implement a simple procedure for computing nth roots using fixed-point, average-damp, and the repeated procedure of exercise 1.43. Assume that any arithmetic operations you need are available as primitives. Doing experiments on the average number of damps to get the fixed-point procedure to converge seems to be:

Using this basis it makes sense to write a procedure discrete-log that computes the number of powers of 2 in a given number. It’s a bit like a very primitive implementation log2 function hence the name. Discrete-log is \( \Theta(\log_2 n) \) because it halves the number of computations every iteration.

(define (root num degree)
  (define (discrete-log n)
    (if (< n 2)
      0
      (+ 1 (discrete-log (/ n 2)))))
  (define (compose f g)
    (lambda (x) (f (g x))))
  (define (repeated-compose f n)
    (if (< n 2)
      f
      (compose f (repeated-compose f (- n 1)))))
  (define (average-damp f)
    (lambda (x) (/ (+ x (f x)) 2)))
  (let ((number-of-compositions (discrete-log degree))
	(initial-function (lambda (x) (/ num (expt x (- degree 1))))))
    (cond ((= degree 0) 1)
          ((= degree 1) num)
	  (else
	    (fixed-point 
	     ((repeated-compose average-damp number-of-compositions) initial-function)
	     1.0)))))

(define (fixed-point f guess)
  (define error 0.001)
  (define (close-enough? x y) (< (abs (- 1 (/ x y))) error))
  (define (try guess)
    (let ((new-guess (f guess)))
      (if (close-enough? guess new-guess)
        new-guess
	(try new-guess))))
  (try guess))

> (root 2 0) 
1
> (root 2 1) 
2
> (root 2 2) 
1.4142135623746899
> (root (expt 2 50) 50) 
1.9999956962054166
> (root 0.00000001 2) 
1.0000000000082464e-4

This program summarizes most of Chapter 1. It has lexical scope, passing functions as parameters, functions that construct and return other functions and the square root algorithm with an improved close-enough? procedure from exercise 1.7. The repeated-compose and discrete-log could be done iteratively instead of recursively like this.

(define (repeated-compose f n)
  (define (compose f g)
    (lambda (x) (f (g x))))
  (define (iter n func)
    (if (< n 2)
      func
      (iter (- n 1) (compose f func))))
  (iter n f))

(define (discrete-log n)
  (define (iter n exponent)
    (if (< n 2)
      exponent
      (iter (/ n 2) (+ 1 exponent))))
  (iter n 0))

Contents