SICP Exercise 1.45 multi average damp

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/y2. 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/y3converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of y  x/y3) 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/yn-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.

 SOLUTION

 Observations from the test below:
1. Fourth and Fifth roots need two average dampings. Three dampings also works but interestingly, it takes more iterations to converge to the same tolerance
2. I tried the 8th root of a number and found that even 3 average dampings were not enough but 4 dampings worked. 5 worked too but again, took more iterations than 4 dampings.

 The code and tests are here.

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 4.18 a alternative strategy for interpreting internal definitions

Exercise 4.18.   Consider an alternative strategy for scanning out definitions that translates the example in the text to (lambda < vars >   (let ((u '*unassigned*)         (v '*unassigned*))     (let ((a < e1 >)           (b < e2 >))       (set! u a)       (set! v b))     < e3 >)) Here  a  and  b  are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the  solve  procedure from section  3.5.4 : (define (solve f y0 dt)   (define y (integral (delay dy) y0 dt))   (define dy (stream-map f y))   y) Will this ...
Read more

SICP Exercise 3.11 make-account internal definitions with local state

Image
Exercise 3.11.    In section  3.2.3  we saw how the environment model described the behavior of procedures with local state. Now we have seen how internal definitions work. A typical message-passing procedure contains both of these aspects. Consider the bank account procedure of section  3.1.1 : (define (make-account balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amount)     (set! balance (+ balance amount))     balance)   (define (dispatch m)     (cond...
Read more

SICP Exercise 3.13 make-cycle

Image
Exercise 3.13.    Consider the following  make-cycle  procedure, which uses the  last-pair  procedure defined in exercise  3.12 : (define (make-cycle x)   (set-cdr! (last-pair x) x)   x) Draw a box-and-pointer diagram that shows the structure  z  created by (define z (make-cycle (list 'a 'b 'c))) What happens if we try to compute  (last-pair z) ? SOLUTION The code is here: Exercise 3.13 make-cycle The box-and-pointer diagrams are here:
Read more