sicp-ex-1.35



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