Binary Exponentiation Algorithm with Example in Java

(1868 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.
610 = 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 610 is 10 as we're naively multiplying 6 to obtain the result. Lets say you have computed the value of 65, now you intend to find the value of 610, how do you do that ?
Method 1:
610 = 65 x 6 x 6 x 6 x 6 x 6
Method 2:
610 = 65 x 65

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.

aN can be written as aN/2 x aN/2 if N is even, and aN/2 x aN/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 aN/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 814.
814 can be written as 87 x 87 (Here N is even)
87 can be written as 83 x 83 x 8 (Here N is Odd)
83 can be written as 81 x 81 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 81, 83, 87 and used them to find 814 If we look step-wise,

• we first calculated the value of 81 and used it to calculate 83,
• 83 is then used to calculate 87,
• 87 calculates 814
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 an/2 x an/2
• if n is odd, return an/2 x an/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); } }