CP Algotithms — Binary Exponentiation
In this article we will have a look at the algorithm of “Binary Exponentiation”. So let’s dive deep into it and know what our task is.
We have to calculate a^x programmatically some of the examples are 3⁵⁰ , 7¹², and so on.
So you must be thinking of ways how it can be solved, you can give it a thought for a few minutes before reading further. Assuming you gave it a thought now let’s see how we can solve this.
Taking 7²⁵ as example to solve this further,
We know that a^x= a^y. a^z and here x = y + z, so we can use this to break our large power into small powers and then multiply them to get our answer. We can also use one more thing to simplify our problem that is, we are aware of decimal and binary numbers so we can convert our decimal power into binary this way:
Converting 25 to binary is (25)10 = (11001)2
If you want to learn more about conversions you can refer to this. Now we can get a very important thing from this binary representation.
Now we get that,
7²⁵= 7¹⁶ * 7⁸ * 7¹
We see here 25 = 16 + 8 + 1, which we looked before and also how we used our binary representation to calculate it. So now the things have become simple as we know the a and then we can find a2 using a * a and then similarly a4 from a2 and so on and then multiply the things which we need to get the answer. As here in this example we will just multiply 7¹ and 7⁸ and 7¹⁶, we won’t multiply 7² and 7⁴ as we don’t need them here.
I hope how we can find the answer is clear mathematically, now the thing which is left to solve this fully is to write a program for it. We will do that too, but before that let’s talk about the time complexity of solving this problem this way.
We also need to recall one more thing that when we convert decimal to binary then the binary number has ⌊log2n⌋+1 example of it is (25)10 = (11001)2
log2(25) = 3.21, and ⌊3.21⌋ = 4
And 4 + 1 = 5 which is the number of digits in binary representation of 25.
We will thus have to multiply log(n) to solve the problem thus the time complexity of the problem is O(log n).
Now coming to the code part this can be done in two ways one is iterative way and the other is recursive way:
Let’s see the iterative way first
long long int binary_exponention(long long int a, long long int n)
{
long long int result = 1;
while(n>0)
{
if(n%2==1)
result = result * a;
a = a * a;
n = n / 2;
}
return result;
}
Here we take our a and n as parameters from the main function and then we first declare the result variable to store the result. We use a while loop for n > 0 and inside the loop we perform 3 operations:
- We check if the n is odd if true then we multiply the result by a, this is a case to handle if the n is odd.
- Then we multiply a by a to get the a2 and we use this for our further calculation;
- We divide the n by 2 so that our power halves this is why our algorithm is called “Binary exponention”.
And then finally we return our result.
We have used here long long int to store large numbers.
2. Recursive way:
We follow following recursive approach expresses the same idea:
long long int binary_exponention_rec(long long int a, long long int n)
{
if(n==0) return 1;
long long int temp = binary_exponention_rec(a, n/2);
long long int result = temp * temp;
if(n % 2 == 1)
result = result * a;
return result;
}
Applications of this algorithm:
- Effective computation of large exponents modulo a number
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
- Effective computation of Fibonacci numbers
- Effective computation of Fibonacci numbers
- Fast application of a set of geometric operations to a set of points
I studied this from https://cp-algorithms.com/algebra/binary-exp.html, you too should have a look at it and learn more about it. This is also my first attempt to write an article, hope you all liked it and learnt something from this. I will be covering all the algorithms from CP-Algorithms and stay tuned for further articles. Thanks for reading and reaching till here :) Happy Learning!
References
1.https://cp-algorithms.com/algebra/binary-exp.html
2. https://www.youtube.com/watch?v=L-Wzglnm4dM&t=629s
3. https://coolconversion.com/math/binary-octal-hexa-decimal/_decimal_number_25_to_binary_
