Binary Exponentiation
Topic Difficulty: EASY
Pre Requisites: Basic Math, general idea on time complexity.
Can we compute powers faster in O(logN) complexity? This topic uses divide and conquer; let's see how we can achieve this complexity …
Let's take this problem — Count good number. Try to spend some time on this problem before proceeding with this article.
This problem somehow boils down to finding expressions like pow(A, B) where A and B are integers.
Here, I am given two numbers, A and B.
My Aim: Compute pow(A, B) efficiently.
- Naive Approach: Just brute force, initialize ans = 1, and perform multiplication with A for B times.
2. Divide and Conquer Style: The main idea is to split the work in half and try to find the results. It can be observed that ….
Analyzing the above relation shows that my power factor gets reduced by half every time. Assuming that each multiplication operation takes O(1) time, our overall complexity becomes O(log(N)), where N is the power to be raised.
Code: (Recursive approach)
We shall see a small example to show how the above code works. Let's say I want to compute pow(3,14)
pow(3,14) = pow(3,7) * pow(3,7)
pow(3,7) = pow(3,3) * pow(3,3) * 3
pow(3,3) = pow(3,1) * pow(3,1) * 3
pow(3,1) = pow(3,0) * pow(3,0) * 3
pow(3,0) = 1
pow(3,1) = 1 * 1 * 3 = 3
pow(3,3) = 3 * 3 * 3 = 27
pow(3,7) = 27 * 27 * 3 = 2187
pow(3,14) = 2187 * 2187 = 4782969
Even an iterative approach exists, which exploits the bitwise representation of my exponent number. Let's take a look at this too.
Main Logic: break down my exponent number into powers of 2 and combine the results.
- Since 14 = 1110 in base 2, 14 = 8 + 4 + 2.
- We can see that: 3¹⁴ = (3⁸)*(3⁴)*(3²)
- Here we are computing values 3¹, 3², 3⁴,3⁸, and exclude 3¹.
Since the number N can have only log(N)+1 bits at most, we can see that we do O(logN) multiplications if we know the powers a¹,a²,a⁴,a⁸,a¹⁶,… so on.
Luckily these numbers {a¹,a²,a⁴,a⁸,a¹⁶,…} can be easily computed by just squaring the previous number.
Summary:
- We can compute power(A, N) in log(N).
Though this may look too easy, this technique has many applications.
In the next blog, we will see about a more powerful technique in CP called Matrix Exponentiation, which has binary exponentiation as its prerequisite.
This article is published as a part of the ‘Algo Reads’ under Spider Research and Development Club, NIT Trichy.
Resource: cp-algorithms
