Off-topic, this is quite the hectic time for me. Between course projects, passion projects, make-a-thons, online programming contests (I’m losing my sanity thanks to CodeChef’s September Long Contest), and university exams and classes, it’s hard to catch some sleep, much less a breather, so the following article will be brief. Anyways, back on topic;

Binary exponentiation is a powerful algorithmic technique, to calculate xy in O(log(y)), as compared to the naïve O(y).

Its uses are many. Apart from just being able to easily exponentiate numbers, its use is best served in the implementation of Matrix Exponentiation, which warrants an article of its own.

Now here’s the important line -

All numbers can be expressed as the sum of powers of 2. 

This is the concept of the binary number system.

5 (Decimal) = 4 + 0 + 1 = 1*(2^2) + 0*(2^1) + 1*(2^0) = 101 (Binary)
9 (Decimal) = 8 + 0 + 0 + 1 = 1*(2^3) + ... + 1*(2^0) = 1001 (Binary)

That being said, the length of this binary equivalent of a decimal number n, will be at most ceil(log(n))+1 where the base of the logarithm is 2. i.e 32 when expressed in binary will fit in 5 bits. 7 in binary, needs 3 bits.

And this is the key, to unlocking the potential of binary exponentiation, as every exponent can be expressed as the product of other smaller exponents that are perfect powers of 2. Let me elaborate –

The core principles that binary exponentiation relies on are

  • The binary equivalent of a number is at most ceil(log(n))+1 in length
  • The high-school math concept of (xa)*(xb) = x(a+b)

The pseudo code, is as follows -

scanf("%d %d",&x,&y);
int final_result=1;
int current_result=x;

//While there are still bits left in y (i.e. while y is not zero)
while(y!=0){

     //if my rightmost bit(LSB) of y is 1, that implies that
     //the current exponent contributes to my final result
     //therefore, I add the current exponent to my final exponent
     //to do which, I multiply my final_result with my current_result 
     if(y&1) final_result*=current_result;

     //As I'm moving in bits from right to left, every bit shift 
     //Implies my potential current exponent contribution doubles
     //Thus, in terms of my current_result, I must square it
     current_result*=current_result;

     //Shift the bits to the right by 1
     y>>=1;
}

printf("%d\n",final_result);

This is why binary exponentiation takes O(log(n)), as the while loop executes only approx. log(n) number of times, while all the operations inside the loop are O(1), constant in runtime.

The way binary exponentiation works, can be explained better with the example of solving for xy  given x and y as input.

Consider the example where y=5.

The code flows as follows -

//Let y=5
while(y){ 
     //Iteration 1:
     //The binary equivalent of y is 101 right now
     if(y&1) //This is equivalent to - if(101 & 001) - which is true
          final_result*=current_result; //this makes final_result=x
     current_result*=current_result;  //current_result = x2
     y>>=1; //y becomes 2 now, as the binary equivalent is now 10

    //Iteration 2:
    //The binary equivalent of y is 10 right now
    if(y&1) //This is equivalent to - if(10 & 01) - which is false
         final_result*=current_result; //This is not executed as no power 
                                       //of 2 contributes to forming x5 
    current_result*=current_result; //current result = x4
    y>>=1; //y becomes 1 now, as the binary equivalent is now 1
     //Iteration 3:
     //The binary equivalent of y is 1 right now
     if(y&1) //This is equivalent to - if(1 & 1) - which is true
          final_result*=current_result; //this makes final_result=x5
     current_result*=current_result; //current_result = x8
     y>>=1; //y becomes 0 now, as the binary equivalent is now 0
     //The loop stops executing
}
printf("%d\n",final_result);

Thus, in 3 loops, x^5 was calculated. Now, the real beauty of this algorithm is better evident over larger exponents. Such as when it occurs that the million-th exponent takes 20 iterations to calculate, compared to the brute force’s 1,000,000.

Now, it’s use is best noted in the aforementioned matrix exponentiation, which allows one to exponentiate matrices in logarithmic time. This is useful especially when recursive functions can be represented as matrices through some linear algebra, but that will have to be covered in an article of its own.