Exercise 1.38 of SICP

Exercise 1.38: In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for e - 2, where e is the base of the natural logarithms. In this fraction, the $N_i$ are all 1, and the $D_i$ are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, …. Write a program that uses your cont-frac procedure from exercise 1.37 to approximate e, based on Euler’s expansion.

Since all the continued fraction works is done from the previous exercise the trickiest part is defining a function for the $D_i$’s. Procedure d should always return 1 except for the special indices. For me it was key to notice that every 3i-1 index, where is is i=1…n, was the even number I care about. And that even number was of the form 2i.

(define n (lambda (i) 1.0))
(define (d i)
  (if (= 0 (remainder (+ i 1) 3))
    (* 2 (/ (+ i 1) 3))
    1))

(define (cont-frac n d k)
  (define (cf i)
    (if (= i (+ k 1))
      0
      (/ (n i) 
         (+ (d i) (cf (+ i 1))))))
  (if (not (> k 0))
    0
    (cf 1)))

(define (cont-frac-iter n d k)
  (define (iter k result)
    (if (= k 0)
      result
      (iter (- k 1) (/ (n k) (+ (d k) result)))))
  (iter k 0))

> (cont-frac n d 11)
.7182818352059925

> (cont-frac-iter n d 11) 
.7182818352059925

$$ e-2 = 0.7182818284590452353 $$

$$ \epsilon = |e-2-0.7182818352059925| = 0.0000000067469472647 $$