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 averagedamped . Unfortunately, the process does not work for fourth roots — a single average damp is not enough to make a fixedpoint search for converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of ) the fixedpoint search does converge. Do some experiments to determine how many average damps are required to compute nth roots as a fixedpoint search based upon repeated average damping of . Use this to implement a simple procedure for computing n^{th} roots using fixedpoint, averagedamp, 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 fixedpoint 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 discretelog 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. Discretelog 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 (discretelog n) (if (< n 2) 0 (+ 1 (discretelog (/ n 2))))) (define (compose f g) (lambda (x) (f (g x)))) (define (repeatedcompose f n) (if (< n 2) f (compose f (repeatedcompose f ( n 1))))) (define (averagedamp f) (lambda (x) (/ (+ x (f x)) 2))) (let ((numberofcompositions (discretelog degree)) (initialfunction (lambda (x) (/ num (expt x ( degree 1)))))) (cond ((= degree 0) 1) ((= degree 1) num) (else (fixedpoint ((repeatedcompose averagedamp numberofcompositions) initialfunction) 1.0))))) (define (fixedpoint f guess) (define error 0.001) (define (closeenough? x y) (< (abs ( 1 (/ x y))) error)) (define (try guess) (let ((newguess (f guess))) (if (closeenough? guess newguess) newguess (try newguess)))) (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.0000000000082464e4
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 closeenough? procedure from exercise 1.7.
The repeatedcompose and discretelog could be done iteratively instead of recursively like this.

(define (repeatedcompose 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 (discretelog n) (define (iter n exponent) (if (< n 2) exponent (iter (/ n 2) (+ 1 exponent)))) (iter n 0)) 