Fast exponentiation algorithm - How to arrive at it? I've been learning about fast exponentiation when I found this algorithm:



int expo(int a, int b) {
  int result = 1;

  while (b) {
    if (b%2==1) {
      result *= a;
    }
    b /= 2;
    a *= a;
  }

  return result;
}


This is supposed to compute $a^b$ in logarithmic time, but I couldn't understand or find anywhere a way to arrive at this procedure, other than by noting that (this particular formula didn't help me in understanding why the algorithm is correct):

$$
x^n = 
\begin{cases}
  1                                          &amp; \text{if $n=0$} \\
  \frac{1}{x}^{-n}                           &amp; \text{if $n&lt;0$} \\
  x \cdot \left( x^{\frac{n-1}{2}} \right)^2 &amp; \text{if $n$ is odd} \\
  \left( x^{\frac{n}{2}} \right)^2           &amp; \text{if $n$ is even}
\end{cases}
$$

From what I understand, the transition from this particular identity to the actual algorithm is quite obvious, but I honestly don't get it and I've worked by hand quite a few examples for this algorithm.

Can anyone explain?
Write $b = b_0 + b_1 2 + b_2 2^2 + ... + b_n 2^n$ where $b_k$ are the binary digits of the representation of $b$ in base $2$. Note that $n$ varies logarithmically with $b$. Then:

$$
a^b = a^{b_0} \cdot (a^2)^{b_1} \cdot (a^{2^2})^{b_2} \cdot ... \cdot (a^{2^n})^{b_n}
$$

The terms where bits $b_k = 0$ evaluate to $1$ and can be skipped. The terms with $b_k = 1$ are of the form $a^{2^k}$ and can be calculated by repeatedly squaring $a$ $k$ times. This is precisely what the posted code does.
Some comments on performance which sadly were too long for a comment.


You can do bit shifts instead of division : 

b &gt;&gt;= 1; // same effect as b/=2, but uses logic instead of expensive integer div instr.


shift all bits left one step. You may need to make sure integers are positive (unsigned int) but will def be faster than risk issuing integer "div" instructions. 
If your hardware has a "find first set bit" instruction (for some reason called ffs), you can use that to get deterministic bound for your loop which will remove branchery at cost of like one pipelineable cpu cycle.
Avoid ifs in loops, may well be better to do 

result *= a*(b&amp;0x1);


replacing the if with logic and arithmetics. Multiplications are very pipelineable and branches risk breaking pipelines. Help the compiler to make the instructions as predictable as possible.