“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…

##
About Alasdair

Capetonian, software developer, land surveyor.