Number Theory - Binary Exponentiation
1.
What is Binary Exponentiation ?
Binary Exponentiation (also know as Fast Exponentiation)
is basically a Technique to calculate A^{n} in O( logn ) isn’t that sound interesting? Yes, right so
let’s dive into it and learn something interesting today.
So be relaxed and keep reading this article to master how binary
exponentiation works…😊
First let take some examples of binary exponentiation:
E.g1.
Input: A = 4, n = 2
Output: 4^{2 }= 16
E.g2.
Input: A = 120, n = 6
Output: 120^{6 }= 2985984000000
Hope now it’s clear to you what we are trying to achieve here !!
So, let’s try to implement Naïve Approach first and then we will optimize
it with some observation as we did in our previous articles.
2. Naive Approach (Brute Force):
As you may have predicted this is a brute force approach so we will be checking for every possible case.
Basically, we will be iterating from 1 to n and in every iteration we will multiply our base (i.e. A) with itself, simple right let’s look at implementation part.
Below is the implementation of naïve approach:
Time Complexity: O(n)
3.
Optimized Approach – O( logn )
As always let’s try to make out some observations to optimize our naïve
approach.
Instead of multiplying each time we will only multiply with the powers of
2, look at below Algorithm for better understanding:
Algorithm for binary exponentiation:
Step1:
Iterate till n > 0
Step2:
In each iteration we will check if our power (i.e. n) is even then we will
do base = base * base, n =
n / 2.
Step3:
else we will do
res = res * base, n = n – 1.
Voila !! we optimized another algorithm with some cool observations.
E.g. let’s find 2^{13} with our optimized method, n = 13, base = 2
a. If our power (i.e. n) is even then we will do base = base * base, n =
n / 2.
b. else we will do res = res * base, n = n – 1.
res |
base |
power(n) |
1 |
2 |
13 (odd) |
1 * 2 = 2 |
2 |
12 (even) |
2 |
2 * 2 = 4 |
12 / 2 = 6 |
2 |
4 * 4 = 16 |
6 / 2 = 3 |
2 * 16 = 32 |
16 |
2 |
32 |
16 * 16 = 256 |
2 / 2 = 1 |
32 * 256 = 8192 |
256 |
0 (STOP) |
Hence, we calculated 2^{13} = 8192 in just 6-7 steps isn’t that awesome?
Now here as we can observe in each step ‘n’ is divided by 2, hence as
discussed in our previous articles if at each step our iteration is
divided by 2 then time complexity becomes logarithmic i.e. logN.
Below is the implementation of optimized approach:
Time Complexity: O( Log(n) )
Note:
In Some problems you need to find Modular also with some P (Prime Number).
So, in that case you just need to change these 2 lines and you are good to
go:
base = ( base * base) % P;
res = ( res * base ) % P;
It is always better to solve a question after you learn a new concept as it helps in making concrete concepts.
So, below are problems which are handpicked by Programmers Army to make your concept more solid which you learned.
1. Problem from CodeForces:
https://codeforces.com/problemset/
problem/913/A
2. Problem from CodeChef:
https://www.codechef.com/problems/
ABX01
We highly recommend to solve above problems if you got stuck read editorials for guidance.
So that’s it for this article we will be coming up with our next article on further topics of number theory very soon till then keep learning, keep coding, keep reading and keep improving !!
Happy Coding
By Programmers Army 😊