SICP exercise 1.38

Problem

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 <math>N_i</math> are all 1, and the <math>D_i</math> 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.

Solution

We need a function d which produces the pattern for the <math>D_i</math>:

i	<math>D_i</math>
1	1
2	2
3	1
4	1
5	4
6	1
7	1
8	6
9	1
10	1
11	8

The pattern has a period of 3: 1, x, 1. <math>D_i</math> is 1 if i mod 3 is either 0 or 1. Otherwise, <math>D_i</math> is <math>2 (\lfloor \frac{i}{3} \rfloor + 1)</math>. Several popular Scheme implementations provide a quotient primitive that'll give us the whole number part of i/3:

(define (d i)
  (let ((rem (remainder i 3)))
    (if (or (= rem 0) (= rem 1))
        1
        (* 2 (+ 1 (quotient i 3))))))

Let's test this function before we go on:

(d 1)

Output:

1

(d 2)

Output:

2

(d 3)

Output:

1

(d 4)

Output:

1

(d 5)

Output:

4

(d 6)

Output:

1

(d 7)

Output:

1

(d 8)

Output:

6

(d 9)

Output:

1

(d 10)

Output:

1

(d 11)

Output:

8

That looks good. Now let's use it to compute an approximation of e, using k terms and the cont-frac function from exercise 1.37 (remember that the continued fraction expansion published by Euler is for e - 2):

(define (cont-frac n d k)
  (define (cont-frac-iter k result)
    (if (= k 0)
        result
        (cont-frac-iter (- k 1) (/ (n k) (+ (d k) result)))))
  (cont-frac-iter k 0))
 
(define (approximate-e k)
  (+ 2
     (cont-frac (lambda (i) 1.0)
             d
             k)))

And now let's test it for k = 10 and k = 20. e is approximately 2.71828183. The results given below were generated using Chicken Scheme 3.1 on a MacBook Pro running OS X 10.5.

(approximate-e 10)

Output:

2.71828171828172

(approximate-e 20)

Output:

2.71828182845905

Note that even 10 steps are sufficient to approximate e to 7 digits.