**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-damp`

ed \( 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:

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

2 | 21 | 1 |

4 | 22 | 2 |

8 | 23 | 3 |

16 | 24 | 4 |

32 | 25 | 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
\( \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))
```