(define (cont-frac n d k) (define (iter i result) (if (= i 0) result (iter (- i 1) (/ (n i) (+ (d i) result))))) (iter k 0)) ; For n(i) = 1, d(i) = 1 the continued fraction sequence is: ; 0/1 1/1 1/2 2/3 3/5 5/8 8/13 13/21 ... ; => kth item is Fib(k)/Fib(k + 1) ; ; Theorem: lim k -> infinity Fib(k)/Fib(k + 1) = 1/phi ; Proof: ; ; lim Fib(k + 1)/Fib(k) = ; k -> infinity ; ; lim phi^(k + 1) - ((1 - sqrt(5))/2)^(k + 1) ; k -> infinity --------------------------------------- = ; phi^k - ((1 - sqrt(5))/2)^k ; lim phi^(k + 1) ; k -> infinity ----------- = (because |(1 - sqrt(5))/2| < 1) ; phi^k ; lim phi = phi ; k -> infinity ; (map (lambda (k) (/ 1.0 ; (cont-frac (lambda (i) 1.0) ; (lambda (i) 1.0) ; k))) (iota 15 1)) ; ; ;Value: (1. 2. 1.5 1.6666666666666665 1.6 1.625 1.6153846153846154 1.619047619047619 1.6176470588235294 1.6181818181818184 1.6179775280898876 1.6180555555555558 1.6180257510729614 1.6180371352785146 1.6180327868852458) ; => 4 decimal places of accuracy for k >= 12 (define phi (/ 1.0 (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 100))) ; 1 ]=> phi ; ; ;Value: 1.618033988749895 ; ; 1 ]=> (/ phi (+ 1 phi)) ; ; ;Value: .6180339887498949 ; ; 1 ]=> (/ 1.0 phi) ; ; ;Value: .6180339887498948 ; ; 1 ]=> (- (* phi phi) phi 1.0) ; ; ;Value: 0. (define (cont-frac-recursive n d k) (define (cf i) (if (> i k) 0 (/ (n i) (+ (d i) (cf (+ i 1)))))) (cf 1))