(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.

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^{10} = 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.

The computational steps involved in the above expansion of 6

Method 1:

6

Method 2:

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.

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^{14}.

8^{14} can be written as 8^{7} x 8^{7} (Here N is even)

8^{7} can be written as 8^{3} x 8^{3} x 8 (Here N is Odd)

8^{3} can be written as 8^{1} x 8^{1} 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^{1}, 8^{3}, 8^{7} and used them to find 8^{14}

If we look step-wise,

- we first calculated the value of 8
^{1}and used it to calculate 8^{3}, - 8
^{3}is then used to calculate 8^{7}, - 8
^{7}calculates 8^{14}

- 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

1 UpvotesUpvote |
0 DownvotesDownvote |

- Java Program to Check if Number is Prime or Not [1062 Views]
- Difference between Arrays.sort() and Collections.sort() [1124 Views]
- CRUD operations Tutorial using Java Spring, Hibernate and MySQL [1280 Views]
- Automorphic Number using Java [1586 Views]
- Difference between Hibernate get and load method [1026 Views]

- Knuth-Morris-Pratt (KMP) Substring Search Algorithm with Java Example [23462 Views]
- How To Win Ludo King Game Every Time [23300 Views]
- Algorithm to find whether number is Armstrong Number or Not [21998 Views]
- Jio Phone hang on LOGO problem Solution - Hard Reset Jio Phone [14502 Views]
- error: Multiple commands produce error in Xcode 10 [12290 Views]