An example: Computing the digits of e

(This example is taken from [Tur82] and it was first implemented in the lazy functional programming language Miranda (a trademark of Research Software Ltd.).)

As an example of a program which uses infinite sequences, consider the problem of computing the digits of the transcendental number e. We would like to calculate as many digits of e as we wish. Notice that the decimal expansion of e is an infinite sequence of integers. (Each integer being a single decimal digit.) We could then use in our implementation the infinite sequence datatype which we have just defined.

The number e can be defined as the sum of a series. The terms in the series are the reciprocals of the factorial numbers.

e = 1/0! + 1/1! + 1/2! + ...
= 2.7182818284590... (base 10)
= 2.1111111111111... (a funny base in which the ith digit has weight 1/i!)
Both the decimal expansion and the expansion in the funny base where the ith digit has weight 1/i! can be expressed as infinite integer sequences. The problem is then to convert from this funny base to decimal.

For any base we have:

Note: The carry factor from the ith digit to the (i-1)th digit is i. I.e. when the ith digit is greater than or equal to i we add 1 to the (i-1)th digit and subtract i from the ith digit.

fun carry(i,cons(x,s))=carry'(i,x,s())
and carry'(i,x,cons(y,s))=cons(x+y div i,lcons(y mod i,s));

fun norm(i,cons(x,s)) ()=norm'(i,x,s())
and norm'(i,x,cons(y,s))=norm''(i,y+9<i,cons(x,norm(i+1,cons(y,s))))
and norm''(i,nocarry,s)=if nocarry then s else carry(i,s);

fun normalise s=norm(2,cons(0,tentimes o s)) ();

fun convert(cons(x,s)) ()=cons(x,(convert o normalise) s);

val e=convert(cons(2,ones));