Custom Big Integer Libraries

Many computer science students are somewhat surprised when they learn that in most programming languages the largest possible integer is only 2,147,483,647. Sure 2 billion is pretty large but when you’re dealing with combinations and permutations, integer values can be astronomically large.

The C# and Java languages have add-on libraries to do Big Integer math. The R language has one too called “gmp”. I decided on a whim to see how hard it’s be to code up a custom Big Integer library. Because I’m currently diving into R, I picked it for my language.

My R language Big Integer library is just a set of functions. A big integer object is just an R list of arbitrary length that contains digits like “6”, “3”, and so on, stored as regular integers. Inefficient but simple.

Coding the addition and subtraction functions wasn’t too hard. Multiplication was a bit of a challenge. Division was quite difficult. When implementing division, I found zero useful information on the Internet. Lots of theory and lots of floating point algorithms. Eventually I just simulated ordinary long division by hand.

Once I had my basic routines created, I used them to code up a factorial(n) function and a choose(n, k) function. All in all, it was interesting, good fun, and gave me many insights into the nuances of R language programming.