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