This past weekend was HackPSU, a typical 24 hour hackathon at Penn State. Without any better idea, my friend, Gage Ames and I decided to break the mold of the typical hackathon projects of games, websites, and mobile apps, and doing something much more nerdy: creating our own arbitrary precision data type in C so we could calculate pi (or any other irrational number) to as many digits as our computers could handle.

We decided to represent each number as a struct with pointers to head of two lists, the mantissa (technically not the correct usage of this term, but close enough for our purposes), or the digits left of the decimal and the decimal part, or the digits right of the decimal. We called this data type “p_num” for “precise number”. We then defined a digit struct which contained the char for the actual digit, and a pointer to the next digit in the list.

Simple. Next would be the process of initializing one of these guys, but due to our decision to represent our numbers in little endian, the init function is unnecessarily complicated, but still interesting. In short, to init a p_num, you call the `init()` function with the mantissa and decimal parts as strings which are then parsed and converted to lists appropriately.

More interesting is the add function. Or should I say functions since we ended up with three functions to add two p_num’s together. Our algorithm is very naive, in that it adds numbers in base 10 just like you learned in elementary school. From a high level, the `add()` function is called with the two p_num’s to be added. This function calls the `add_digits()` function which adds a given digit list together. Inside `add_digits()`, `add_with_carry()` is called which actually adds two given digits and returns a possible carry from the addition. A major memory compromise we made here (and with all other arithmetic functions we wrote) was that we assumed that the first argument to be added would be modified with the result of the addition. The reason for this being that we did not want to create a copy of a potentially huge number. For our purposes, this was fine, but would not bode well for a more generic task. The full source is below, but these two functions are the more interesting parts of the functions needed for the complete addition algorithm.

After addition, we had to tackle multiplication. Here’s where another one of the big mistakes happened: To save time and effort, we decided to perform multiplication as repeated calls to the addition function. But this idea caused a problem because we couldn’t multiply non-whole numbers this way. So instead we decided to move all the decimal digits to the left of the decimal point (move them into the mantissa list), do the multiplication, and then move those digits back to the right of the decimal (back into the decimal list).

Creative? Sure. Messy? Absolutely.

Granted, because we’re working with linked lists, this process isn’t too time consuming since it’s just some iterating and moving pointers around. The full source of the shift functions are below. I’ll skip them here. Below is the multiply function. Due to the nature of multiplying, we were forced to make a copy of one of the passed in p_num’s which involves a confusing copy function which I’ll also skip the finer details of since this isn’t a post on manipulating pointers and list operations.

Here’s where things basically fell off a cliff: the exponentiation function.

Similar to multiplication, we took the shortcut of representing exponentiation as repeated multiplications. However, this time we had a problem that we couldn’t perform exponentiation with non-integer powers. After looking at the formula for approximating pi we were shooting for, we realized that we wouldn’t need to have non-integer powers, so we didn’t account for it. This is still a huge limitation in the exponentiation function though. The real problem with the exponentiation function, though, is that is it slow. I mean really, really slow. All the shortcuts were bound to catch up with us eventually, right? A little further down is the actual execution times for all these functions. I’ll save the surprise (and laughter) for then.

After realizing how slow the exponentiation function was, and because, remember, this was a 24 hour hackathon and it was approaching the last third of the 24 hours, we were tired, frustrated, and just sick of working on this so we essentially dropped the project at this point… or at least for the time being. It would be nice to come back at take a new look at this whole thing with some fresh eyes.

The code above doesn’t sell the whole story though. We had a bunch of other functions that needed written to make the above code work. Apart from the typical list operations such as appending to the head, appending to the tail and reversing the list, we had a comparison and copy list function. Even the print function was more complicated than I’m used to. To the print the list, we had to reverse it then print it out and finally, reverse it again so the list was back in the correct order used for the arithmetic functions. All in all, it was a ton of work for very little payoff. There should also be a free function, because as it stands, no memory is ever free’d leading to a whole slew of memory leaks, but that wasn’t a high priority at the time.

The full source of all these functions are below, but first, let’s take a look at just how slow this thing was.

Here’s a simple main file that just adds two files. Timing is done with the built-in bash time command. To compile we used the `O3` flag in GCC, which does actually speed it up considerably compared to no optimization at all. The executable is appropriately called “irrational”.

The add function executes in a pretty reasonable amount of time for some simple numbers.

It even works well when we use some very large, and very precise numbers, such as:

For the skeptics, here’s Wolfram’s computation since this number is obviously too precise for a regular calculator.

Multiplication also isn’t too terrible, but does choke on large numbers. I’ll stick with a simple case here.

As you can see, this is starting to push it. 2.5 seconds is not an acceptable calculation time for something so simple. On the up side, my TI-84 calculator, gives a less precise answer for this case than this program does. Again, for verification, Wolfram’s computation, which does handle the calculation with the same (probably better actually) precision that we do here.

Finally, exponentiation. Let’s keep it very simple so the program finishes before next month.

That’s right, 14.5 seconds to calculate 24. This obviously isn’t scaling well. Sure, we could do some optimizations to make it faster, but it seems to me like a whole new approach is needed.

The next day, I resorted to libgmp, the GNU multiple precision library, and lo and behold, I had pi calculated accurately to 10,000 places in a few hours. With some changes in the approximation formula, I now have it calculating to 1.5 million digits in under 2 minutes, but that’s the topic of another post entirely.

In conclusion, lessons learned:

• Don’t try to write your own arbitrary precision data type and accompanying functions in fewer than 24 hours.
• There’s a fine line between trading computation time for memory. Moderation is key.
• A singly-linked list is definitely the wrong implementation; a doubly-linked list probably isn’t much better.

As promised, the full source.

p_num.h:

p_num.c:

Last but not least, a super small Makefile: