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