Choose the right language for the job

“When all you have is a hammer, everything looks like a nail”

So I tacked Question 16 of Project Euler today. In short you need to deal with a massive number, far bigger than the maximum integer or even long integer supported by C/C++.

So I realised that this limitation would then require a numerical method solution. I delved into this and after 45 minutes or so came up with a neat, safe, robust and fast computation that worked. Hooray! My algorithm is essentially doing a long-multiplication as learnt by 10 year old school kids.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define width 500

int main(int argc, char *argv[])
{
    int a[2][width];
    memset(&a[0], 0, 2 * width * sizeof(int));
    a[0][width - 1] = 1;

    int limit = 2 == argc ? atoi(argv[1]) : 1000;
    for (int i = 0; i < limit; i++)
    {
        int this_idx = i % 2;
        int next_idx = (i + 1) % 2;

        int carry = 0;
        for (int j = width - 1; j >= 0; j--)
        {
            int v = a[this_idx][j];
            int w = (v << 1) + carry;
            a[next_idx][j] = w % 10;
            carry = w / 10;
        }
    }

    int final_idx = limit % 2;
    int solution = 0;
    for (int k = 0; k < width; k++)
        solution += a[final_idx][k];
    printf("%d\n", solution);
    return 0;
}

This is clearly C code. I know the language, feel very comfortable with it, and is always my preferred choice.

I posted my valid answer and as normal I’m then granted access to the forum for that question where others post their comments on their solution. I quickly realised that others came up with much simpler solutions by choosing a language that supports big numbers.

I revisited the question using python. I don’t know python well at all, but the solution became so trivial once the stumbling block of large number support had been removed. I rewrote it in about 5 minutes, if that.

#!/usr/bin/env python

a = 2 ** 1000
b = 0
for c in str(a):
    b += int(c)
print b

Five lines! I should have thought more about the tool, and less about finding a work-around solution with my preferred tool.

A poor consolation that matters little, is that the C version executes six times faster! But then that’s just me grumbling and muttering…