SICP Exercise 1.35: Fixed points and the Golden ratio

From SICP section 1.3.3 Procedures as General Methods

Exercise 1.35 asks us to show that the golden ratio ϕ is a fixed point of the transformation x → 1 + 1 / x. We're then asked to use this fact to compute ϕ by means of the fixed-point procedure defined earlier in the chapter.

First we can show that ϕ is one of the roots of x → 1 + 1 / x. We learned the value of ϕ in section 1.2.2 is (1 + √5) / 2, or approximately 1.618.

x = 1 + 1 / x

If we multiply both sides by x we get:

x² = x + 1
x² - x - 1 = 0

Now if we use the quadratic equation (or cheat and use WolframAlpha like I did) we find that the roots of the equation are:

x = 1/2(1 - √5)
x = 1/2(1 + √5)

Computing ϕ by means of the fixed-point procedure is fairly straightforward since the procedure is already given.

(define tolerance 0.00001)

(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))

The fixed-point procedure takes a function and an initial guess. Since we're trying to find a point where

x = 1 + 1 / x

that's the function we need to pass. The initial guess can really be just about anything, but we already know that we're trying to prove the fixed point is around 1.6, so let's try an initial value close to that.

> (fixed-point (lambda (x) (+ 1 (/ 1 x))) 2.0)
1.6180327868852458

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.