Calculating Pi on a Business Card using TeX
I've seen a trend recently about putting some fun piece of code on the back of a business card. For no reason in particular, I decided that I wanted to do something similar! And since I've been sinking a bunch of my time into TeX recently, I decided to implement something in TeX.
TeX can't (or at least makes it really hard to) do anything like make an interactive game or spit out fancy bitmap raytraced graphics, so I had to come up with something that was mostly text-based. I remembered a recent post on Pi day about Google calculating some ridiculous number of digits of Pi, so I thought there might be some simple algorithms for calculating pi. Also, TeX doesn't really have easy support for floating point numbers, so something that only does integer arithmetic would be ideal.
Pretty quickly, I learned about a tiny C program that Dik T. Winter wrote to calculate digits of pi. It only used integer math, so it seemed like a good fit for what I was looking for! After doing some deobfuscation and then doing some digging, I eventually found a good description of the algorithm that it was using.
With the algorithm in hand, I started implementing. Unfortunately, I ran into a snag immediately: the original algorithm used a really big array (with more than 3 times the number of spaces as digits you want to calculate) to store intermediate remainders as it was calculating, but TeX doesn't have the concept of arrays. There are a static number of variable registers (in plain TeX, 256) that could be used as an array, but that would only let me calculate about 70 digits of pi. I decided that that's how it was going to go and started implementing the rest of the algorithm, using the registers as the array.
Things came together nicely. There was basically one big loop to calculate the final product, and then a few helper macros to do things like calculate remainders and add some formatting (The original program spits out “31415926...” but I wanted it to actually show “3.1415926” with the decimal point). I eventually got things working, and it was pretty cool! TeX, a markup language with no floating point numbers, was calculating decimal digits of an irrational number.
However, I wasn't terribly satisfied with the result. I wanted to be able to calculate an arbitrary number of digits of pi and not be limited by the number of registers available. I thought about the different kinds of values in TeX, and decided that “token lists”, which could store (almost) unlimited amounts of token characters, could probably be retrofitted to store unlimited numbers of integers. So, I set out to build a real array.
Actually, I figured that due to how the algorithm works, I didn't need the full indexing power of an array. Since the algorithm linearly traverses the array and just edits the one value that it's looking at, I could make do with 2 stacks: I'd pop values off of one stack and then push the new values onto the second stack. Then, after each iteration I'd replace the (empty) first stack with the new second stack. Building a stack using token lists turned out to be fairly straightforwards:
First, we create
\nextlist as aliases for two token list registers:
We're going to store our lists like
;<number>;<number>;<number>;:. This allows us to distinguish the different values, as well as tell where the end of the list is.
Our first macro pops a value off of
\currlist and places it in the variable pass in as
We're effectively passing the current value
\currlist and the variable we want to be setting to the
macro that does the real work,
\popcurrinner. We have to
\expandafter to get TeX to
\the\currlist to its value (instead of just passing
the literal tokens
Now we write that inner macro. Using the power of parameter
expansion, we can pull out the first value from the list (which is
recognized by the ; surrounding it) as
#1, store it in the
appropriate variable (which is now
#3), and then finally
\currlist to be the remainder of the
% Store the first value in #3
% Set the new \currlist
The last thing we need is the ability to push to our lists. This is
relatively simple, but we have to use a bunch
\expandafter to get things to evaluate correctly. This
is the function for pushing to
\currlist, and there's an
analagous one for
\nextlist. Since we're never popping
\nextlist, this is all we need.
Armed with our new infinite stack abilities, we can now calculate as many digits of pi as we want! For the final design I put on my business card, I calculated just enough digits to fill up the back of a business card, and then printed a couple business cards with the generated output on the back instead of the code.
I had to minify the code to fit on a business card, so the resulting code isn't terribly understandable, but that's okay. Hopefully nobody tries to actually read it off of the business card anyways!
See the whole TeX program here