The Magic Pantry

I had absolutely no sleep at all last night, which is why I spent today in a stupor, content with reading news and pottering about rather than Doing Something Challenging.

This explains why I started doing some vanity searches this afternoon, digging up an old web-page of mine from the mid-1990′s. Yes, it used TABLEs for formatting (back then, it was common to UPPERCASE your HTML). Yes, it included a count of page views at the bottom of each and every page. And, yes, it even included a link to my “hotlinks” which I could access when using “Netscape” from home, over my swanky 14.4 dialup connection (presumably when I could drag myself away from playing with my PlayStation).

One of my old web pages was about number problems. I used to have fun writing programs to solve puzzles such as these by brute force:

Which numbers satisfy the following property… the sum of the individual digits of the number raised to the power of that digit is equal to the number itself? For the purpose of this problem, we define 0^0=0.

For example, the number 3435 is known to have this property, since 3^3 + 4^4 + 3^3 + 5^5 = 3435.

This problem proved rather easy to solve. We know that no numbers above 10*9^9 (about 4e9) can have this property, simply because the sum will always be less than the original number. Therefore we can solve the problem by brute force, using unsigned 32-bit integers.

I wrote such a program, and it took a few hours to execute on our SGI Onyx computer. The solution set is { 0, 1, 3435, 438579088 }.

And here’s my program:

#include <stdio.h>

typedef unsigned long INT;

int main(int argc, char **argv)
{
	INT number;
	INT sum;
	INT num;
	INT power[]={0,1,4,27,256,3125,46656,823543,16777216,387420489};

	for(number=0; number<4e9; ++number)
    {
		sum=0;
		num=number;

		do {
			if((sum+=power[num%10])>number) break;
		} while(num/=10);

		if(number==sum) printf("%d\n", number);
	}

	return(0);
}

It’s almost unbelievable that such a program used to take “a few hours” to run on a machine that was, at the time, a veritable power horse. Today I compiled and ran it on my grungy lappy. It burned one core for a few minutes to find the same solution. All the while, my computer remained snappy, and I actually became impatient waiting for the answer. What have we become? Why aren’t we doing more, now that we all carry around supercomputers with us?

Funny thing is, my website was averaging 1800 hits per day back in the mid-90′s. This blog, by comparison, barely manages 10. Well, phooey.

Update: Optimisations

On my desktop at work, this same program ran in 150 seconds, using a quarter of the total processing power of the machine. That’s something like 26 million numbers checked every second. That would have seemed like magic 13 years ago, when the Onyx was checking half a million numbers each second.

Beetlefeet asked about the optimisations mentioned in my comment below. Each optimisation sped up processing by a factor of 10 or so. I’ve re-run them on my desktop. The first completes in 45 seconds, and the second completes in around 5 seconds, so they still count for something!

The first optimisation, by David Conrad, worked by keeping a running total of the current value, modifying it each time around the loop based on how the digits in the number changed. It printed the result whenever the number equalled this running total. Here’s the code:

#include <stdio.h>

int digit[10] = {0,0,0,0,0,0,0,0,0,0};
long diff[10] = {-387420489,1,3,23,229,2869,43531,776887,15953673,370643273};

int main(void)
{
    unsigned long x = 0, val = 0;
    int i;
    while (x < 4e9) {
        if (x == val) printf("%lu\n", x);
        i = 0;
        digit[i] = digit[i] == 9? 0 : digit[i]+1;
        val += diff[digit[i]];
        while (digit[i] == 0) {
            i++;
            digit[i] = digit[i] == 9? 0 : digit[i]+1;
            val += diff[digit[i]];
        }
        x++;
    }
    return 0;
}

The second optimisation, by Geoff Bailey (AKA Fred the Wonder Worm), was really clever; it maintained a running total too, but worked by looping over 10 variables, one that represented each digit. Here’s the code:

#include <stdio.h>

typedef unsigned long   ulong;

long diffs[] = {
    1, 3, 23, 229, 2869, 43531, 776887, 15953673, 370643273, -387420489
};

main()
{
    ulong       sum, n;
    int         i0,i1,i2,i3,i4,i5,i6,i7,i8,i9;

    sum = 0;
    n = 0;

#define LOOP(var, lim, code)	\
    for (var = 0; var < lim; sum += diffs[var++])	code

    LOOP(i9, 4,
    LOOP(i8, 10,
    LOOP(i7, 10,
    LOOP(i6, 10,
    LOOP(i5, 10,
    LOOP(i4, 10,
    LOOP(i3, 10,
    LOOP(i2, 10,
    LOOP(i1, 10,
    LOOP(i0, 10,
    {
        if (n == sum)
            printf("%lu\n", n);
        n++;
    }
    ))))))))))
    return 0;
}

I guess that optimisation and obfuscation are closely related (although you don’t always get faster code by making it harder to understand).