Geek alert. I was reading in a book that the late great physicist Richard Feynman once invented a computer science algorithm for computing logarithms that's still being used. While I can hardly hope to match his brilliance in just about any area, it did remind me of an algorithm I came up with, way back in high school I think, that (as far as I know) is mine (although it's probably been invented independently a number of times). I doubt it's of any serious significance but I like it just the same. So here it is.

I was writing a routine to compute the average of a big list of numbers. The typical way you do it is to just sum the numbers, and divide by the size of your list, like this:


sum <-- 0;
for i <- 1 to n
sum <-- sum + number[i];
average = sum / n;


This routine didn't work for me, because I noticed that sum kept overflowing. But I realized that if you compute the average as you go along, you don't need to keep the the running sum, because sum is always going to be equal to average*i, where i is the number of items you've processed so far. So you can compute a new average by using that as your sum, adding the new number, and dividing by the new count of items, like this:


average <-- 0;
for i <-- 1 to n
average <-- ( average*(i-1) + number[i] ) / i;


But here average*(i-1) can just as easily overflow as the running sum we kept in the first example. However, at this point you can just manipulate the algebra terms so that no big multiplication needs to take place:


average <-- 0;
for i <-- 1 to n
average <-- average - average/i + number[i]/i;


So there you go -- an averaging routine that can compute the average of just about as many numbers as you want without overflowing. I've actually used this in real applications before.

We now return you to your regularly scheduled dog stories.