Number Theory - Binary Exponentiation

1. What is Binary Exponentiation ?

Binary Exponentiation (also know as Fast Exponentiation) is basically a Technique to calculate Aⁿ 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…😊

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:

Voila !! we optimized another algorithm with some cool observations.

E.g. let’s find 2¹³ 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¹³ = 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:

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.

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 😊