Computing e - Revisited

I decided to revisit the problem of computing digits of e after talking to someone who thought that a spigot algorithm would work without a loss of precision. I felt pretty embarrassed when it took about 30 seconds to find some code that did exactly what I wanted it to. It took only a few minutes to convert the algorithm from Javascript into C, it works great!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(int argc, const char *argv[])
{
	int i;
	int len;
	int *a;
	int x = 0;

	if (argc < 2) {
		fprintf(stderr, "Usage: %s n\nn - number of decimal places\n", argv[0]);
		return -1;
	}

	len = strtol(argv[1], NULL, 10);
	if (!len) {
		fprintf(stderr, "Error parsing argument\n");
		fprintf(stderr, "Usage: %s n\nn - number of decimal places\n", argv[0]);
		return -1;
	}
	len += 9;
	a = malloc(len*sizeof(int));
	if (!a) {
		fprintf(stderr, "malloc error\n");
		return -1;
	}
	a[0] = 0;
	a[1] = 0;
	for (i = 2; i < len; i++) {
		a[i] = 1;
	}
	printf("2.");
	while (len > 9) {
		for (i = len; i > 0; i--) {
			a[i] = x%i;
			x = 10*a[i-1] + x/i;
		}
		len--;
		printf("%d", x);
	}
	printf("\n");

	return 0;
}

Then after consulting some documentation to look up the finer points of Bash syntax, I rewrote it:

#!/bin/bash

if [[ ( $# < 1 ) || !( $1 =~ ^[0-9]+$ ) ]]; then
	echo "Usage: $0 n"
	echo "   n - number of decimal places of e to output"
	exit -1
fi

len=$(($1 + 9))

A[0]=0
A[1]=0
for (( i = 2; i < $len; i++ )); do
	A[$i]=1
done

echo -n "2."

X=0
while [[ $len -gt 9 ]]; do
	for (( i = $len; i > 0; i-- )); do
		A[$i]=$(( $X % $i ))
		X=$(( 10 * ${A[$i-1]} + $X / $i ))
	done
	len=$(( $len - 1 ))
	echo -n "$X"
done
echo

And it works! I tested it and compared it to the first several thousand digits that are listed on http://apod.nasa.gov/htmltest/gifcity/e.1mil and they were identical.

It’s amazing how these problems can initially seem so difficult, but once the correct approach to the problem is found, the solution is actually quite simple.

Older

Newer