Number Theory - Binary Exponentiation


1. What is Binary Exponentiation ?

Binary Exponentiation (also know as Fast Exponentiation) is basically a Technique to calculate An 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: 42 = 16

E.g2. Input: A = 120, n = 6
Output: 1206 = 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 213 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 213 = 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.

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 😊