## Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

# 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 $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.

## Solution

We need a function d which produces the pattern for the $D_i$:

i $D_i$
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. $D_i$ is 1 if i mod 3 is either 0 or 1. Otherwise, $D_i$ is $2 (\lfloor \frac{i}{3} \rfloor + 1)$. 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.