# Computing nth roots of a number - SICP exercise 1.45

From SICP

Exercise 1.45:

We saw in 1.3.3 that attempting to compute square roots by naively finding a fixed point of 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 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 x/y^3 converge.

On the other hand, if we average damp twice (i.e., use the average damp of the average damp of 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 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.

The definitions of the helper procedures stated in the exercise are:

• (fixed-point f x) applies f to x repeatedly until x does not change very much.
• ((average-damp f) returns a procedure that gets the average of x and the value of (f x).
• (repeated f n) returns a procedure with one argument x and applies f to x n times.

First, here is the definition for the newton's method. This code is from the book:

(define dx 0.00001)

(define (deriv g)
(lambda (x)
(/ (- (g (+ x dx)) (g x))
dx)))

(define (newton-transform g)
(lambda (x)
(- x (/ (g x)
((deriv g) x)))))

(define (fixed-point-of-transform
g transform guess)
(fixed-point (transform g) guess))


Here is my code for computing nth root.

I first created a procedure called least-expt that computes how many times average-damp should be applied based on the number of roots. Through some experiments, I found that the number of times average-damp should be applied is the value x-1 of 2^x where x will never be greater than the number of roots. The least-exp procedure does this process exactly.

(define (least-expt n)
(define (least x)
(if (> (expt 2 x) n)
(- x 1)
(least (+ x 1))))
(least 1))


Here is my main procedure:

  (define (roott n)
(lambda (x)
(fixed-point-of-transform
(lambda (y)
(/ x
(expt y (- n 1))))
(repeated
average-damp
(least-expt n))
1.0)))


Now, as far as I know, this procedure works exactly fine. But I am extremely confused by this part of the exercise:

Assume that any arithmetic operations you need are available as primitives.

I don't understand this statement. I did not use any unusual arithmetic operations. Are there something in my code that should take advantage of these arithmetic operations ?

How can I improve this code and make it faster?