SICP Exercise 1.38: Calculating e as a k-Term Continued Fraction

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.

We know from the previous exercise, where we used cont-frac to approximate 1/ϕ, that if N_i are all 1 then we can express this using (lambda (i) 1.0). So all we have to do to approximate e is to figure out how to calculate the sequence for D_i (namely 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...), produce a lambda expression for this, plug them into cont-frac and add 2 to the result.

Let's have a look at the sequence: 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, .... Notice how the numbers come in groups of 3: {1, 2, 1}, {1, 4, 1}, {1, 6, 1}, {1, 8, 1}, .... In each group of three the first and third elements are 1, while the middle element is 2g, where g is the index of the group. How can we calculate this from the sequence 1, 2, 3, ..., k?

Well, first of all, note that we can determine whether or not term i is the middle of a group of 3 by looking at i modulo 3: if it's in the middle of a group of 3 then i modulo 3 will be 2, and we need to calculate 2g, otherwise it's the first or third element of the group, and so D_i will be 1. If it's in the middle of a group of 3 then we can calculate the group number by adding 1 to it (which will make it a multiple of 3) and then dividing by three.

Using this we can produce a procedure for approximating e:

(define (approximate-e k)
  (+ (cont-frac (lambda (i) 1.0)
                (lambda (i) (if (= (remainder i 3) 2)
                                (* 2 (/ (+ i 1) 3))
                                1))
                k)
     2))

And then we can put it into practice. e is approximately 2.7183 to four decimal places, so let's see how quickly our procedure produces a number of similar accuracy:

> (approximate-e 1)
3.0
> (approximate-e 2)
2.6666666666666665
> (approximate-e 3)
2.75
> (approximate-e 4)
2.7142857142857144
> (approximate-e 5)
2.71875
> (approximate-e 6)
2.717948717948718
> (approximate-e 7)
2.7183098591549295