The Limber Lambda

A colleague brought my attention to this brain-teaser, from Project Euler:

Having a Unix background, my first instinct was to fire up bc which I know can deal with integers of any size you like—such a calculator is known as an arbitrary precision calculator.

Here’s the one-liner, together with execution time:

Now, if you’re a Java programmer, you’ll know about java.math.BigInteger which is the implementation of an arbitrary precision integer.  Sadly, in the .NET world there is no built-in equivalent (soon to change in .NET 4.0).

What I did find interesting though was that the default (and only) implementation of integer in a lot of languages, including Python and Ruby is of the arbitrary precision variety (this also applies to Scheme and Lisp).  Since I have two implementations of python installed on my PC, namely cpython and IronPython, I could benchmark them from the command line.

First, cpython: And … IronPython:

Unfortunately the initialisation of the python runtime puts a nasty skew on our comparison in the case of IronPython.

Somehow, that just feels like cheating though, and even though there aren’t any set rules on Project Euler about how you come to the answer, of course, you just feel like you should be doing it a clever way; read: no use of a big integer library, built-in or otherwise.

The solution is simple, but deceptively so—why would we need to keep track of all those “more significant digits” if we never need them?  As long as we keep our eight byte integer from overflowing, we should be fine.  Hence our BigInteger-free C# version:

class Program 
{
    static void Main(string[] args)
    { 
        var largest = 10L*10*10*10*10*10*10*10*10*10; 
        var tot = 0L; 
        for (int i = 1; i < 1001; i++)
        { 
            var exp = 1L; 
            for (int j = 0; j < i; j++)
                exp = (exp * i) % largest;
            tot = (tot + exp) % largest;
        }
        Console.WriteLine(tot);
    } 
}

And the result: