So I was brushing up on my algorithms knowledge and I stumbled across something that rather blew my mind. It turns out I’ve been computing powers the wrong way all this time.
The straightforward means of computing powers (ie. exponents) is to simply multiply the base times itself for each value of the exponent. Take for example:
This would become:
5 * 5 * 5 * 5 * 5 * 5 * 5 * 5
This means that a naive computation of 5^8 is would take eight steps, so a^n is an O(n) computation. However, it’s possibly to compute powers much faster than that. Once you realize:1
a^n = a^ceil(n/2) * a^floor(n/2)
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 respectively. With this process, a^n is an O(lg n) computation, which is a lot faster. A way to visualize this is:
5^8 = 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 = (((5 * 5) * (5 * 5)) * ((5 * 5) * (5 * 5)))
So, instead of multiplying by 5 eight time sequentially, one can simple 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 performed a quick test and this code is indeed much faster than the naive power function for large values of n. Now my question is why I never thought of doing this? The math is really simple and conceptually this is straightforward. I usually visualize numbers in terms of their factors anyway so this should have been obvious to me. Now, it’s unusual for me to have to implement my own power function, but it does happen, so maybe I just haven’t been faced with it enough? No, I think the real answer is that I simply didn’t think of computing powers as something that ought to be optimized. It’s ‘math’ I probably thought, it’s a basic function, it’s not optimizable. That’s a problem and it makes me wonder where else I’ve failed to make something as fast as it could be. Maybe some reviews of old code are in order?
- ceil and floor are rounded up and down to the nearest integer respectively. ↩