We'll look at two performance tweaks for the Power1 class shown previously.
First, we need to switch to a better algorithm. Then, we will require a better algorithm combined with memoization, which involves a cache; therefore, the function becomes stateful. This is where callable objects shine.
The first modification is to use a divide-and-conquer design strategy. The previous version chopped the computation of into steps; the loop carried out n individual multiplication operations. If we can find a way to split the problem into two equal portions, the problem decomposes into steps.
For example, pow1(2,1024), the Power1 callable, performs 1,024 individual multiplication operations. We can optimize this down to 10 multiplications, a significant speedup.
Rather than simply multiplying by a fixed value, we'll use the fast exponentiation algorithm...