Exercise1-44 <---> Exercise1-46

Exercise 1.45

We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of y↦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 y↦x/y² . Unfortunately, the process does not work for fourth roots -- a single average damp is not enough to make a fixed-point search for y↦x/y³ converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of y↦x/y³ ) 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↦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.

Ru: Русский текст упражнения

Scheme solution:

(define (nth-root n)
  (lambda (x) (fixed-point ((repeated average-damp (floor (/ (log (+ n 0.9)) (log 2))))
                             (lambda (y) (/ x (expt y (- n 1)))))
                            1.0)))

Exercise1-44 <---> Exercise1-46

Comments

Floor looks like it always rounds down (it isn't covered in SICP at this point). I implemented round-down like this: (define (round-down x) (let ((rounded (round x))) (if (< rounded x) rounded (- rounded 1)))) I also did the repeated function a bit different. Unless I'm missing something, the number of repeats is equal to the square root of the closest integer less than n. This is implemented like this: (define (average-damp f) (lambda (n) (average n (f n)))) (define (sqrt b) (fixed-point (average-damp (lambda (y) (/ b y))) 1.0)) (define (n-root b n) (fixed-point ((repeated ; repeat average-dump average-damp (round-down (sqrt n))) ; we repeat as many times as the sqrt of n (lambda (y) (/ b (fast-expt (- n 1))))) 1.0)) I may be wrong of course!

Posted by DanielMoerner at 2008-12-25 09:07:09

(define (nth-root x n) (define func (lambda (y) (/ x (expt y (- n 1))))) (fixed-point ((repeated average-damp (truncate (/ (log n) (log 2)))) func) 1.0));; i used truncate, the problem said "Assume that any arithmetic operations you need are available as primitives."

Posted by 195 at 2009-02-04 19:46:37 X

Add your comment Markup