Fast Power-Exponentiation by Squaring
We know how to find 2 raised to the power 10. But what if we have to find 2 raised to the power very large number such as 1000000000? Exponentiation by Squaring helps us in finding the powers of large positive integers. Idea is to the divide the power in half at each step.
9 ^ 5 = 9 * 9 * 9 * 9 * 9
// Try to divide the power by 2
// Since the power is an odd number here, we cannot do so.
// However there's another way to represent
9 ^ 59 ^ 5 = (9 ^ 4) * 9
// Now we can find 9 ^ 4 and later multiple the extra 9 to the result
9 ^ 5 = (81 ^ 2) * 9
Effectively, when power is not divisible by 2, we make power even by taking out the extra 9. Then we already know the solution when power is divisible by 2. Divide the power by 2 and multiply the base to itself.
Below is the code snippet for Fast Power-Exponentiation by Squaring
#include <iostream>
int power(int x, int y, int p) {
// Initialize result
int res = 1;
// Update x if it is more than or equal to p
x = x % p;
// In case x is divisible by p
if (x == 0)
return 0;
while (y > 0) {
// If y is odd, multiply x with result
if (y % 2 == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
int main() {
// Find 9^5 mod 1000000007
std::cout << power(9, 5, 1000000007) << std::endl;
return 0;
}
public class Main {
static int power(int x, int y, int p)
{
// Initialize result
int res = 1;
// Update x if it is more than or equal to p
x = x % p;
// In case x is divisible by p
if (x == 0)
return 0;
while (y > 0) {
// If y is odd, multiply x with result
if ((y & 1) == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
public static void main(String[] args)
{
// Find 9^5 mod 1000000007
System.out.println(power(9, 5, 1000000007));
}
}
def power(x, y, p):
# Initialize result
res = 1
# Update x if it is more than or equal to p
x = x % p
# In case x is divisible by p
if x == 0:
return 0
while y > 0:
# If y is odd, multiply x with result
if y & 1:
res = (res * x) % p
# y must be even now
y = y >> 1 # y = y/2
x = (x * x) % p
return res
print(power(9, 5, 1000000007))
function power(x, y, p) {
// Initialize result
let res = 1;
// Update x if it is more than or equal to p
x = x % p;
// In case x is divisible by p
if (x === 0)
return 0;
while (y > 0) {
// If y is odd, multiply x with result
if ((y & 1) === 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Main method
function main() {
// Find 9^5 mod 1000000007
console.log(power(9, 5, 1000000007));
}
// Call the main method
main();
Output
59049
Maths for Data Structure and Algorithms (DSA) | A Complete Guide
Maths is a fundamental component of learning Data Structure and Algorithms, just like in programming. Maths is primarily used to evaluate the effectiveness of different algorithms. However, there are situations when the answer requires some mathematical understanding or the problem has mathematical characteristics and certain problems demand more than just code. They require a mathematical perspective and a recognition of patterns and characteristics that go beyond the syntax of programming languages. Therefore, understanding maths is essential to know data structures and algorithms. So here in this Maths Guide for Data Structure and Algorithms (DSA), we will be looking into some commonly used concepts of Maths in DSA.
Table of Content
- GCD and HCF (Euclidean Algorithm)
- Divisors of a number
- Prime numbers using Sieve of Eratosthenes
- Square root
- Modular Arithmetic
- Fast Power-Exponentiation by Squaring
- Factorial of a number
- Fibonacci Number
- Catalan Numbers
- Euler Totient Function
- Prime numbers & Primality Tests
- Prime Factorization & Divisors
- Chinese Remainder Theorem
- Practice Problems based on Maths for DSA
- Most Frequently Asked Questions (FAQs)