SICP - Solution: Exercise 1.45

October 29, 2018

Exercise 1.45 #

We saw in 1.3.3 that attempting to compute square roots by naively finding a fixed point of ${y\mapsto 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\mapsto 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 ${y\mapsto x/y^3}$ converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of ${y\mapsto x/y^3}$) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute $n^{\text{th}}$ roots as a fixed-point search based upon repeated average damping of $y\mapsto x/y^{n-1}$. Use this to implement a simple procedure for computing $n^{\text{th}}$ 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 #

Experimentation #

First, let’s implement a function nth-root-damped that allow us to quickly test the parameters nth and damping:

(define (compose f g)
  (lambda (x)
    (f (g x))))

(define (repeated f n)
  (if (= n 1)
      f
      (compose f (repeated f (- n 1)))))

(define (power x n)
  (if (= n 1)
      x
      (* x (power x (- n 1)))))

(define (nth-root-damped x nth damp)
  (fixed-point
    ((repeated average-damp damp)
    (lambda (y)
      (/ x (power y (- nth 1)))))
   1.0))

By varying the parameters, we can see for $x=2$ the minimal number of damping needed for the function to converge:

The pattern where the number if minimal damp do converge looks to increase every time the nth is reaching a power of 2. By searching the documentation, it seems that we can compute minimal damp using a base 2 logarithms and the floor function to provide an integer (needed for computing the power):

(floor (log 63 2))
> 5

(floor (log 64 2))
> 6

Solution #

We can insert that in our solution that becomes:

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

We can try the solution with large nth to check if it holds:

(display (nth-root 2 258))
> 1.0026902132630033

Open question #

• Where does this pattern of convergence for log base 2 comes from?