Mastering JavaScript Functional Programming - Second Edition

Decrease and conquer – doing powers

Another classic example has to do with calculating the powers of numbers in an efficient way. If you want to calculate, say, 2 to the 13th power (2¹³), then you can do this with 12 multiplications; however, you can do much better by writing 2¹³ as the following:

= 2 times 2¹² = 2 times 4⁶ = 2 times 16³ = 2 times 16 times 16² = 2 times 16 times 256¹ = 8192

This reduction in the total number of multiplications may not look very impressive, but, in terms of algorithmic complexity, it allows us to bring down the order of the calculations from O(n) to O(lg n). In some cryptographic-related methods, which have to raise numbers to really high exponents, this makes a very important difference. We can implement ...