**Exercise 1.45:** We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of 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-damp**ed . Unfortunately, the process does not work for fourth roots — a single average damp is not enough to make a **fixed-point** search for converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of ) 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 . Use this to implement a simple procedure for computing n^{th} 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:

Degree of root | Power of 2 | Number of average damps |

2 | 2^{1} |
1 |

4 | 2^{2} |
2 |

8 | 2^{3} |
3 |

16 | 2^{4} |
4 |

32 | 2^{5} |
5 |

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 log_{2} function hence the name. Discrete-log is because it halves the number of computations every iteration.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
(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.

1 2 3 4 5 6 7 8 9 |
(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)) |

1 2 3 4 5 6 |
(define (discrete-log n) (define (iter n exponent) (if (< n 2) exponent (iter (/ n 2) (+ 1 exponent)))) (iter n 0)) |