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

0 UpvotesUpvote |
0 DownvotesDownvote |

- java.util.Arrays Common Used Methods [266 Views]
- Difference between StringBuilder insert and append method [182 Views]
- Create Dynamic Pagination using Java Spring Boot, Hibernate and MySQL [3699 Views]
- Difference between Java Spring and Java Swing [305 Views]
- Java Program to Concatenate two strings without using string functions [1377 Views]

- Knuth-Morris-Pratt (KMP) Substring Search Algorithm with Java Example [6877 Views]
- Pseudocode and Algorithm to find whether number is Armstrong Number or Not [6382 Views]
- How To Win Ludo King Game Every Time [6250 Views]
- error: Multiple commands produce error in Xcode 10 [4737 Views]
- Create Dynamic Pagination using Java Spring Boot, Hibernate and MySQL [3699 Views]