Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 1.35

From Drewiki
Jump to: navigation, search

Problem

Show that the golden ratio <math>\phi\,</math> (see section 1.2.2 of the text) is a fixed point of the transformation <math>x \mapsto 1 + 1/x</math>, and use this fact to compute <math>\phi\,</math> by means of the fixed-point procedure.

Solution

The fixed point of the function is

<math>1 + 1/x = x\,</math>

Solving for x, we get

<math>x^2 = x + 1\,</math>

<math>x^2 - x - 1 = 0\,</math>

Using the quadratic equation to solve for x, we find that one of the roots of this equation is <math>\frac{1 + \sqrt{5}}{2}</math>, which is the golden ratio <math>\phi\,</math> (approximately 1.6.18).

Using the fixed-point procedure from the text to compute the numeric value:

(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))
 
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)

The result produced by Chicken Scheme 3.1 on Mac OS X 10.5 on a MacBook Pro is

1.61803278688525
Personal tools