So I was brush­ing up on my algo­rithms knowl­edge and I stum­bled across some­thing that rather blew my mind. It turns out I’ve been com­put­ing pow­ers the wrong way all this time.

The straight­for­ward means of com­put­ing pow­ers (ie. expo­nents) is to sim­ply mul­ti­ply the base times itself for each value of the expo­nent. Take for example:

5^8

This would become:

5 * 5 * 5 * 5 * 5 * 5 * 5 * 5

This means that a naive com­pu­ta­tion of 5^8 is would take eight steps, so a^n is an O(n) com­pu­ta­tion. How­ev­er, it’s pos­si­bly to com­pute pow­ers much faster than that. Once you realize:¹

a^n = a^ceil(n/2) * a^floor(n/2) 

Which implies:

a^n = (a^(n/2))^2       - for even values of n
a^n = a(a^floor(n/2))^2 - for odd values of n

What this means is that:

5^8 = (5^4)^2 = ((5^2)^2)^2
or
3^7 = 3(3^3)^2 = 3(3(3^2))^2

Which only requires 3 and 4 steps respec­tive­ly. With this process, a^n is an O(lg n) com­pu­ta­tion, which is a lot faster. A way to visu­al­ize this is:

5^8 = 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 = (((5 * 5) * (5 * 5)) * ((5 * 5) * (5 * 5)))

So, instead of mul­ti­ply­ing by 5 eight time sequen­tial­ly, one can sim­ple square 5 three times. Code for this would look like:

(defun power (a n)
  (case n
    (0 1)
    (1 a)
    (2 (* a a))
    (t (cond ((evenp n) (power (power a (/ n 2)) 2))
             ((oddp n) (* a (power (power a (floor (/ n 2))) 2)))))))

I per­formed a quick test and this code is indeed much faster than the naive power func­tion for large val­ues of n. Now my ques­tion is why I never thought of doing this? The math is really sim­ple and con­cep­tu­ally this is straight­for­ward. I usu­ally visu­al­ize num­bers in terms of their fac­tors any­way so this should have been obvi­ous to me. Now, it’s unusual for me to have to imple­ment my own power func­tion, but it does hap­pen, so maybe I just haven’t been faced with it enough? No, I think the real answer is that I sim­ply did­n’t think of com­put­ing pow­ers as some­thing that ought to be opti­mized. It’s ‘math’ I prob­a­bly thought, it’s a basic func­tion, it’s not opti­miz­able. That’s a prob­lem and it makes me won­der where else I’ve failed to make some­thing as fast as it could be. Maybe some reviews of old code are in order?

1. ceil and floor are rounded up and down to the nearest integer respectively. ↩