2
\$\begingroup\$

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?

\$\endgroup\$

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.