Tuesday, November 13, 2012

Calculus of Algorithms

No, that's not really English; how about "Four orders of magnitude performance improvement".  Nope, I’m still trying to impress the boss.  Here: "Creating fast software" - that's better.  One of the most useful tools of my career is a mathematical idea I toyed with in high school - in those days (35 years ago)  I walked around with a (paper) notebook and 3 ink pens in my shirt pocket (seemed like they were always running out of ink).  I spent years using all my free time trying to figure out what I called "shadow math".  A professor would call it "finite integral calculus of a recursive field"

Here's a simple example: Suppose you have a calculation "NUMBER plus 5" meaning that you have a number in mind and I'm naming it "NUMBER".  The result of the calculation is that now you have a new number (that we'll call "RESULT") and it's 5 bigger than the original number ("NUMBER").  Let's name the calculation "CALC".  So far we have:

"NUMBER" - some number you know but are unwilling to say (not because it's evil or anything, you're just enjoy keeping a secret!)

"CALC" - a definition of a way to modify "NUMBER"; in this case it's not a secret: "NUMBER + 5".

"RESULT" - the result of "CALC"; we're calling it "RESULT" because if you wanted to keep "NUMBER" secret, you're probably not going to want to say
"RESULT"'s value either.

What if, for reasons obviously far away from common sense, you want to perform CALC over and over again; and each time use RESULT for NUMBER?

Step 1: create the first RESULT with CALC and NUMBER.  So in shorthand: RESULT <= CALC(NUMBER), or specifically RESULT is NUMBER plus 5.

Step 2: create a new RESULT with CALC and RESULT.  i.e. RESULT <= CALC(RESULT) (written backwards; sorry, still trying to sound smart), or specifically RESULT plus 5 is the new RESULT.

Step 3: repeat step 2 over and over again.  RESULT is going to be bumping up by 5 over and over again. let's call the count of the number of times step 2 gets done "TIMES", since it's obviously also a secret; maybe it's not a secret - I just don't know what value it is; that's why it has a name.

Now you have a new value- you started with NUMBER and used CALC a lot (TIMES times to be precise) and the result is RESULT (still a secret, you're happy because now you have three!).

And, now you know how to program a computer, iPhone, or Android; that’s all that programs and apps are: written down steps and made-up names when your not sure what the value is going to be.  Bad news though; you're only an average programmer at this point.  To get the big bucks, you have to do something a little different:

Step 1: calculate 5 times TIMES plus NUMBER - i.e. use multiplication (i.e. better math), and don’t use repeating steps.

It's that simple; except for the final step - you'll need to show your boss that the new calculation (call it "TURBOCALC") is about a billion times faster (when TIMES is a billion) and that now the people who really care about the CALC result can have it instantaneously on their iPhone instead of waiting till tomorrow AND they're lining up in the streets, bubbly, and delighted to pay good money for TURBOCALC.

Epilogue
It's really amazing what the opportunities for improvement are out there.  Sure, this example had two variables and one (simple) calculation.  Real world examples have hundreds (or thousands) of variables, many calculations, and lots of special rules - but the concept is the same.

No comments:

Post a Comment