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:

• take the integer part as a decimal digit;
• take the remaining digits, multiply them all by ten and renormalise (using the appropriate carry factors);
• repeat the process with the new integer part as the next decimal digit.

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));

NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX