Integer Exponentiation Algorithm Explained
Published: 2020-06-11 13:54:20

There's a commonly known algorithm for calculating an integer power of an integer.

```cpp
unsigned int power(unsigned int base, unsigned int exponent)
{
    unsigned int result{ 1 };
    unsigned int multiplier{ base };

    while (exponent)
    {
        if (exponent & 1)
        {
            result *= multiplier;
        }
        exponent >>= 1;
        multiplier *= multiplier;
    } 
    return result;
}
```

This code is quite fast and effective. Let's dig through it and figure out what's going on behind the scenes.

Any unsigned integer is represented in the memory as a sequence of bits, where each bit is responsible for the presence of a certain power of 2 in our number. For instance, a decimal number `25` becomes `11001` when converted to the binary and here's why:
{% katex %}
 25 = \textcolor{green}{\mathbf{1}}\cdot2^{4} + \textcolor{green}{\mathbf{1}}\cdot2^{3} + \textcolor{red}{\mathbf{0}}\cdot2^{2} + \textcolor{red}{\mathbf{0}}\cdot2^{1} + \textcolor{green}{\mathbf{1}}\cdot2^{0}
{% endkatex %}

or, in general form, if {% katex inline %} \overline{a_{n}a_{n-1}...a_{2}a_{1}a_{0}} {% endkatex %} is an arbitrary binary number, where {% katex inline %} a_{i} {% endkatex %} is a {% katex inline %} i{% endkatex %}-th binary digit, then we can calculate its decimal value like this:
{% katex %}
\boldsymbol{a_{n}}\cdot2^{n} + \boldsymbol{a_{n-1}}\cdot2^{n-1} + ...  + \boldsymbol{a_{2}}\cdot2^{2} + \boldsymbol{a_{1}}\cdot2^{1} + \boldsymbol{a_{0}}\cdot2^{0}\quad(1)
{% endkatex %}

We're about to calculate the value of the expression 

{% katex %}
base^{exponent}
{% endkatex %}

Our exponent can be represented as a binary using formula (1). Thus, the whole expression can be rewritten as:

{% katex %}
base^{\lparen\boldsymbol{a_{n}}\cdot2^{n} + \boldsymbol{a_{n-1}}\cdot2^{n-1} + ...  + \boldsymbol{a_{2}}\cdot2^{2} + \boldsymbol{a_{1}}\cdot2^{1} + \boldsymbol{a_{0}}\cdot2^{0}\rparen}
{% endkatex %}

We can use a product rule and get rid of that addition in the exponent. Now our initial expression takes this form:

{% katex %}
base^{\boldsymbol{a_{n}}\cdot2^{n}} \cdot base^{\boldsymbol{a_{n-1}}\cdot2^{n-1}} \cdot ... \cdot base^{\boldsymbol{a_{1}}\cdot2^{1}} \cdot base^{\boldsymbol{a_{0}}\cdot2^{0}} 
{% endkatex %}

Needless to say, {% katex inline %} a_{i} {% endkatex %} is still a binary digit, hence, it is either 0 or 1 and nothing more. So, our expression turns out to be just a product of different powers of *base*, and, what is extremely useful for us, those powers are powers of 2 themselves!
For instance, we're told to evaluate {% katex inline %} 7^{13} {% endkatex %}. Without doubt, `13` as a decimal is `1101` as a binary. Therefore, we can rewrite our expression this way:

{% katex %}
7^{13} = 7^{2^{3}} \cdot 7^{2^{2}} \cdot 7^{2^{0}} = 7^{8} \cdot 7^{4} \cdot 7^{1}
{% endkatex %}

Fortunately, those powers of 7 are extremely easy to evaluate: we just have to square our *base* (i.e. 7) n times, where n is a corresponding power of 2. That means if we want to calculate {% katex inline %} 7^{8} {% endkatex %}, we can square 7 three times one after another:

{% katex %}
7^{8} = ((7^{2})^{2})^{2}
{% endkatex %}

Great! It's time to focus on the original algorithm. At the beginning we've got the `result` variable, initialized with `1`. We're going to multiply this variable by different powers of `base` (and, as mentioned above, those powers are powers of 2 themselves), which we're going to store in our `multiplier` variable.

By the way, variable `multiplier` is used there just to make our code easier to understand. We could square `base` variable instead.

The `while`-loop goes through our `exponent` extracting (via `>>=` operator) bits one by one from low-order to high-order ones. At the same time, our `multiplier` variable is squaring on each iteration, holding original `base` value in the power of the *n*-th power of 2 on the *n*-th iteration step (a little bit tricky, yeah). Take a look at the corresponding part of our code:

```cpp
    while (exponent)    //if exponent is not 0
    {  
        //...

        exponent >>= 1; //cutting off the low-order bit
        multiplier *= multiplier;   //squaring the multiplier
    } 
```

The `if`-condition within `while`-loop checks whether current *n*-th bit is `1`. If so, it's time to multiply our `result` by {% katex inline %} base^{2^{n}}{% endkatex %}. And, coincidentally, our `multiplier` holds exactly that value!

That's how it works.