<< Previous exercise (1.34) | sicp-solutions | Next exercise (1.36) >>
First, we prove that the transformation x -> 1 + 1/x yields phi:
x = 1 + 1/x x^2 = x + 1
This second equation is the definition of phi from 1.2.2. We can also derive the explicit formula for phi from this equation by recasting as a quadratic and solving with the quadratic formula (discarding the negative root):
x^2 - x - 1 = 0 x = ( 1 + sqrt(5)) / 2
The code is thus simple:
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
Sample run on MzScheme with routine to print x and f(x) in (fixed-point):
x = 1.0 and f(x) = 2.0 x = 2.0 and f(x) = 1.5 x = 1.5 and f(x) = 1.6666666666666665 x = 1.6666666666666665 and f(x) = 1.6 x = 1.6 and f(x) = 1.625 x = 1.625 and f(x) = 1.6153846153846154 x = 1.6153846153846154 and f(x) = 1.619047619047619 x = 1.619047619047619 and f(x) = 1.6176470588235294 x = 1.6176470588235294 and f(x) = 1.6181818181818182 x = 1.6181818181818182 and f(x) = 1.6179775280898876 x = 1.6179775280898876 and f(x) = 1.6180555555555556 x = 1.6180555555555556 and f(x) = 1.6180257510729614 x = 1.6180257510729614 and f(x) = 1.6180371352785146 x = 1.6180371352785146 and f(x) = 1.6180327868852458 x = 1.6180327868852458 and f(x) = 1.618034447821682 x = 1.618034447821682 and f(x) = 1.618033813400125 x = 1.618033813400125 and f(x) = 1.6180340557275543 x = 1.6180340557275543 and f(x) = 1.6180339631667064 x = 1.6180339631667064 and f(x) = 1.6180339985218035 x = 1.6180339985218035 and f(x) = 1.618033985017358 x = 1.618033985017358 and f(x) = 1.6180339901755971
Another solution using average damping:
(fixed-point (lambda (x) (average x (+ 1 (/ 1 x)))) 1.0)