Iterative Implementation of Binary Exponentiation
#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long b) {
long long result = 1;
while(b) {
if (b & 1)
result = result * a;
a = a * a;
b >>= 1;
}
return result;
}
int main() {
cout<<power(2, 12)<<"\n";
return 0;
}
public class Main {
public static long power(long a, long b) {
long result = 1;
while (b > 0) {
if ((b & 1) == 1) {
result *= a;
}
a *= a;
b >>= 1;
}
return result;
}
public static void main(String[] args) {
System.out.println(power(2, 12));
}
}
def power(a, b):
result = 1
while b:
if b & 1:
result = result * a
a = a * a
b >>= 1
return result
if __name__ == "__main__":
print(power(2, 12))
using System;
class Program {
// Function to calculate power
static long Power(long a, long b)
{
long result = 1;
while (b > 0) {
if ((b & 1) == 1)
result *= a;
a *= a;
b >>= 1;
}
return result;
}
static void Main() { Console.WriteLine(Power(2, 12)); }
}
// Function to calculate the power of a number
function power(a, b) {
let result = 1;
while (b > 0) {
// If b is odd, multiply result by a
if (b & 1) {
result *= a;
}
// Square a
a *= a;
// Divide b by 2 using bitwise right shift
b >>= 1;
}
return result;
}
// Main function
function main() {
// Output the result of power(2, 12)
console.log(power(2, 12));
}
// Call the main function
main();
Output
4096
Even though, both the iterative and recursive approach have the same time complexity, the iterative approach is still faster because there are no overheads for recursive calls.
Binary Exponentiation for Competitive Programming
In competitive programming, we often need to do a lot of big number calculations fast. Binary exponentiation is like a super shortcut for doing powers and can make programs faster. This article will show you how to use this powerful trick to enhance your coding skills.
Table of Content
- What is Binary Exponentiation?
- Why to Use Binary Exponentiation?
- Idea Behind Binary Exponentiation
- Recursive Implementation of Binary Exponentiation
- Iterative Implementation of Binary Exponentiation
- Use Cases of Binary Exponentiation in Competitive Programming
- Practice Problems on Binary Exponentiation for Competitive Programming