Fun With Math

Knowing in principle how to do something and then actually doing it are two very different things. I recently had need of very large integer support. 128 bits would do, but native hardware support stops at 64 bits on most architectures. So I wrote a simple templated class that is a two-digit number, where each digit is an integer of some built-in type.

This is what the class looks like:
There's a high digit and a low digit, and I keep the most significant bit of the low digit as a carry bit to detect overflow or underflow.

Implementing add and subtract was easy:

But multiply turned out to be a pain. I want to use the native multiply available for an integral type, but multiplying doubles the number of bits you need. If you multiply two 16 bit numbers, you need 32 bits to hold the result in the worst case. Addition is less brutal - you need only 1 extra bit in the worst case.

Here's the solution that I came up with for multiplication. I won't show the helper routines used, because they're straightforward, but here's the single digit multiply.

Seems a lot more tedious than you would expect, but basically I split each single digit into a pair of half sized digits so I can use the native multiply, then shift and add the all of the partial products up.

I have tested the code on 8, 16, and 32 bit digits with 10 M random inputs each, and it seems to behave correctly.

Since I had never done this before, I figured it was worth a blog post. It had been a while.