SICP Exercise 1.35

Question

Show that the golden ratio \(\phi\) (section 1.2.2) is a fixed point of the transformation \(x\mapsto 1+\frac{1}{x}\), and use this fact to compute \(\phi\) by means of the fixed-point procedure.

Answer

We know from section 1.2.2 that \(\phi ^2=\phi +1\). We can use this information to show that the above transformation will converge to \(\phi\).

So why does this work? Well, because they are the same equation. If we divide \(\phi^2=\phi+1\) by \(\phi\) on both sides, we get \(\phi=1+\frac{1}{\phi}\), which, of course, is the equation from the question.

(define tolerance 0.0001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(fixed-point (λ (x) (+ 1 (/ 1 x))) 1.0)

The results are very close to the actual value of \(\phi\):

1.6180555555555556