226 Digits of e

Description

Wayumbe Rubyists,

The mathematical constant e is the unique real number such that the value of the derivative (slope of the tangent line) of the function f(x) = e^x at the point x = 0 is exactly 1. The function e^x so defined is called the exponential function, and its inverse is the natural logarithm, or logarithm to base e.1

e is one of the most important numbers in mathematics, alongside the additive and multiplicative identities 0 and 1, the constant π, and the imaginary unit i. These are the five constants appearing in one formulation of Euler’s identity.

This week’s quiz is to write a Ruby program that can compute the first 100,000 digits of e.

Have fun!

Summary

This quiz harkens back to another mathematically themed computation competition Digits of Pi (#202). Many of the same techniques that can be applied to the computation of pi can be applied to the computation of e, and there are some surprising results.

Jack Rouse used the fast converging continued fraction series from Wikipedia to create a short program that quickly calculates e to 100_000 digits. Jack’s solution is quite quick, yielding the output within several seconds.

Jean-Julien Fleck started with a benchmark of the the standard library call and estimated that it would take 10**5 seconds to compute the first 100_000 digits. Jean-Julien provides a handy one liner that can be used in irb:

fact = 1 ; (1..34_000).inject(1) {|sum,i| fact *= i ; sum + Rational(1,fact)}

This computation makes use of the Taylor series definition. The results use Rational, so can be quite slow, it is advised to start with a smaller number of iterations, possibly 500 or so.

Thorsten Hater created a program based on the spigot algorithm from Rabonitz and Wagon. From the paper:

> This algorithm is a “spigot” algorithm: it pumps out digits one
> at a time and does not use the digits after they are computed [...];
> the entire algorithm uses only ordinary integer arithmetic on 
> relatively small integers.

The paper is actually about computing the digits of pi with the same method, but in doing so covers the case of e, which is simpler. An interesting approach, and worth looking at if you are into mathematics.

Benoit Daloze explored eight different methods of computing e with a focus on breadth rather than depth. See them all in the attached solutions supplement. Benoit also came across this interesting bit of information:

lim(n->inf) ((2n+1)/(2n-1))**n    => e
lim(n->0)   ((2n+1)/(2n-1))**n    => π

Jay Anderson and and David Springer used the Taylor series definition of e, which is quite fast at converging and delivering 100_000 digits. These solutions are much faster that other Taylor series implementations because they use only integer arithmatic and a very simple loop.

Here is Jay Anderson’s solution:

digits = 100000
fudge = 10
unity = 10**(digits + fudge)

e = unity
n = unity
i = 0

while (n>0)
  i += 1
  n /= i
  e += n
end

e /= 10**fudge
p e

Setting unity to be 10^digits shifts everything into the integers so that floating point math won’t be required. The extra fudge factor ensures that there aren’t rounding errors near the end. Each step of the loop requires only an increment, an integer division, and an addition. Notice how the division in the loop accumulates the factorial, because the result of 1/2 is stored when it is divided by 3 it is set equal to 1/3!. The loop terminates when the series term becomes 0, i.e. too small to add anything that will matter within the chosen number of digits.

Thanks everyone for your solutions to the quiz!

Digits of e (#226) - Solutions

P.S. Brian Candler linked to an xkcd comic involving e and π, not all contributions need to be code.


Friday, January 08, 2010