Powers Algorithm

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:


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:1

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
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. 

Last update: 29/9/2011

blog comments powered by Disqus