June 07, 2012

I saw a job posting on Hacker News with an interesting problem which promptly sucked me in.

Send a bash program that calculates Euler’s number to N decimal places (where N is specified on the command line) to

I thought it looked like an interesting problem so I opened up Vim and started working on it in my language of choice, C, with the intention of porting it to Bash after I got it working.

The first step was determining how to calculate e programmatically, which brought me to Wikipedia. The infinite series at the top of the article seemed like a good place to start so I implemented it quickly and hackily.

That worked for the first 11 digits (2.71828182845), but failed on the 12th
(2.71828182845**8** instead of 2.7828182845**9**)

I thought that the issue would be the denominator of the infinite series being
extremely large and overflowing, but that’s not the case. Before that happens,
the double holding `e`

loses precision after too many divide-by-10s.

I did some Googling (actually DuckDuckGo-ing, but that doesn’t have the same ring to it) and found a website describing how one person wrote a program to do exactly what I wanted. It referenced a paper on an finding digits of pi. I read through the paper and concluded that I am bad at reading and understanding academic papers, especially since the code snippets are written in Haskell, a language that I don’t know. I was able to read the blog post though and implement it in C (after spending way too much time figuring out the matrix math).

This algorithm works using a different infinite sequence, but it still has the
same precision errors. After 15 digits, the first error occurs
(2.718281828459045**3** instead of 2.718281828459045**2**). I spent a long time
going over the code and couldn’t find any errors that were causing my program to
fail while it seemed to work for the guy who’s blog I was reading. I came to the
conclusion that the author must have used BigInteger or another library.

I still really wanted to solve the problem, so I decided to give it one last
shot. I decided to go back to the original problem statement, and I wrote it in
Bash. It isn’t written using *only* Bash, but at least it gives me some closure.
It works for up to 1,000,000 digits of *e*.

If I have time, and motivation, I may revisit this problem. The next step I’d try would be to use a fixed point library, such as the GNU MPFR.