SICP Exercise 1.35: Calculating ϕ as a Fixed Point

Show that the golden ratio ϕ (section 1.2.2) is a fixed point of the transformation x → 1 + 1/x, and use this fact to compute ϕ by means of the fixed-point procedure.

We can show that ϕ is a fixed point of the transformation x → 1 + 1/x in (at least) a couple of ways. One way is it start from what we know about ϕ and prove that ϕ = 1 + (1/ϕ). If we can do this then we show that it corresponds to the transformation.

What do we know about ϕ? Well, we know that ϕ² = ϕ + 1, so let's see what we can do with that:

  ϕ2 = ϕ + 1
⇒ ϕ = (ϕ + 1)/ϕ
⇒ ϕ = (ϕ/ϕ) + (1/ϕ)
⇒ ϕ = 1 + (1/ϕ)

Another way is to start from the transformation, treat it as the equation x = 1 + 1/x and solve the equation for x:

  x = 1 + 1/x
⇒ x - 1 - 1/x = 0
⇒ x2 - x - 1 = 0

We now have a quadratic equation with quadratic coefficient of 1, linear coefficient of -1 and and -1 as the constant term, so we can solve this using the quadratic formula:

x = -(-1) ± √((-1)2 - 4·1·(-1))
               2·1
  = 1 ± √(1 + 4)
         2
  = 1 ± √5
      2

So we have two solutions for x: (1 + √5)/2 and (1 - √ 5)/2. In other words ϕ and Ψ respectively.

Having shown it's a fixed point of the transformation, we can use fixed-point to compute ϕ by converting the transformation to a procedure. Since we've just learned about lambda, let's use that:

> (fixed-point (lambda (x) (+ 1.0 (/ 1.0 x))) 1.0)
1.6180327868852458

In section 1.2.2 we were told that ϕ ≈ 1.6180, so this looks like a reasonable approximation.