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))

(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) 
       (lambda (y) 
         (/ x 
            (expt y (- n 1))))
        (least-expt n))

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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.