Binary Exponentiation Algorithm

[5072 views]

Binary Exponentiation is a fast and efficient way of computing exponent of a number. The conventional method takes n steps to compute nth power of any number but Binary Exponentiation takes log(n) steps to do the same work.

Need of Binary Exponentiation:

Lets say you are asked to compute 10th power of 6. A naive approach would be to multiply 6 ten times to get the result.
6¹⁰ = 6 x 6 x 6 x 6 x 6 x 6 x 6 x 6 x 6 x 6
But can we do better ? The answer is YES.

Any algorithm can be made efficient if we can identify the repetitive steps involved. Like in binary search we don't need to search the whole array for the searching element, rather we have to only look at one half of the array as we know that other half won't have the element.
The computational steps involved in the above expansion of 6¹⁰ is 10 as we're naively multiplying 6 to obtain the result. Lets say you have computed the value of 6⁵, now you intend to find the value of 6¹⁰, how do you do that ?
Method 1:
6¹⁰ = 6⁵ x 6 x 6 x 6 x 6 x 6
Method 2:
6¹⁰ = 6⁵ x 6⁵

Which of the above 2 methods mentioned would you follow ? The second one right ? Because second method involves a lot less computations than the first one. We'll now see how to apply this approach in a more organized manner.

Divide and Conquer approach:

The idea is to divide our problem into smaller sub-problems and use their results to compute the original problem. We can apply divide and conquer to this problem because of the associative property of multiplication.

a^N can be written as a^N/2 x a^N/2 if N is even, and a^N/2 x a^N/2 x a, if N is Odd.

We just divided our original problem into 2 smaller sub-problems, of N/2 size. Now we just have to compute the value of first sub-problems and use it's result into the other one, as both the sub-problems are same. i.e, Once we compute the value of a^N/2, we can just multiply it 2 times to get the result, at the first step itself, we reduced our computations by the factor of 2.

Lets compute the value of 8¹⁴.
8¹⁴ can be written as 8⁷ x 8⁷ (Here N is even)
8⁷ can be written as 8³ x 8³ x 8 (Here N is Odd)
8³ can be written as 8¹ x 8¹ x 8 (Here N is Odd)

Conventional method would require us to do the multiplication 14 times. But here's we did it more efficiently. Let's analyse our solution.
We calculated some powers of 8 and used them, skippping some other powers. We just computed 8¹, 8³, 8⁷ and used them to find 8¹⁴

If we look step-wise,

we first calculated the value of 8¹ and used it to calculate 8³,
8³ is then used to calculate 8⁷,
8⁷ calculates 8¹⁴

If we look at the flow, at every level, the problem is divided into two equl sub-parts, this gives this algorithm its name "Binary Exponentiation", and the time comlexity is O(logn).

Psudocode of Binary Exponentiation:

Number: a & Power : n

if n is 0, return 1
if n is 1, return n
if n is even, return a^n/2 x a^n/2
if n is odd, return a^n/2 x a^n/2 x a

Binary Exponentiation Java Program:

public class JavaTest{ static long binaryExponentiation(int a, int n){ if(n==0) return 1; if(n==1) return a; long result = binaryExponentiation(a, n/2); if(n%2==0) return result*result; else return result*result*a; } public static void main(String[] args){ int number = 5; int power = 11; long result = binaryExponentiation(number, power); System.out.println("Result is : "+result); } }