DSA - Mathematical Algorithms
Mathematical algorithms are well-defined procedures that are used in solving mathematical problems related to data structures. We can see its application in competitive programming, data science and other complex mathematical concepts. These algorithms teach us how to solve a given problem by thinking logically and efficiently.
Important Mathematical Algorithms
Some of the important mathematical algorithms are −
Euclid's Algorithm
Sieve of Eratosthenes
Binary Exponentiation
Modular Arithmetic
Here is the detailed explanation −
Euclid's Algorithm
Euclid's algorithm, also referred to as the Euclidean algorithm, is a method that is used to compute GCD of two given integers. The term GCD is an abbreviation that stands for greatest common divisor. The GCD is also termed as highest common factor(HCF). It is defined as the largest integer that divides a given set of numbers.
Suppose, a given set of integers are A and B. Here's how the Euclidean Algorithm works to find their GCD −
If A is equal to 0 and B is the non-zero integer, then GCD(A, B) is B.
The GCD of two integers A and B remains unchanged on subtracting the smaller integer from the larger one. Therefore, repeating this process several times will result in GCD.
Recursively compute A mod B and when it becomes 0, we will get our GCD which is B.
Example
In the following example, we are going to illustrate how Euclid's algorithm works.
#include <stdio.h>
int findGrtCmFact(int a, int b) {
if (b == 0) {
return a;
} else {
return findGrtCmFact(b, a % b);
}
}
int main() {
int valOne = 52;
int valTwo = 28;
printf("The GCD of %d and %d is: %d
", valOne, valTwo, findGrtCmFact(valOne, valTwo));
return 0;
}
#include <iostream>
using namespace std;
int findGrtCmFact(int a, int b) {
if (b == 0) {
return a;
} else {
return findGrtCmFact(b, a % b);
}
}
int main() {
int valOne = 52;
int valTwo = 28;
cout << "The GCD of " << valOne << " and " << valTwo << " is: " << findGrtCmFact(valOne, valTwo) << endl;
return 0;
}
public class GrtComFactr {
public static int findGrtCmFact(int a, int b) {
if (b == 0) {
return a;
} else {
return findGrtCmFact(b, a % b);
}
}
public static void main(String[] args) {
int valOne = 52;
int valTwo = 28;
System.out.println("The GCD of " + valOne + " and " + valTwo + " is: " + findGrtCmFact(valOne, valTwo));
}
}
def findGrtCmFact(a, b):
if b == 0:
return a
else:
return findGrtCmFact(b, a % b)
valOne = 52
valTwo = 28
print("The GCD of {} and {} is: {}".format(valOne, valTwo, findGrtCmFact(valOne, valTwo)))
Output
The GCD of 52 and 28 is: 4
Sieve of Eratosthenes Algorithm
The Sieve of Eratosthenes algorithm is a way used for identifying prime numbers within a given range. The naive approach to finding prime numbers is by iterating over each number and checking whether the current number is prime or not. However, it is not the optimal solution.
Here's how the Sieve of Eratosthenes works −
Start with a list of numbers from 2 up to N. Initially, consider all these numbers as potential primes.
Begin with the first prime number, which is 2. Mark all multiples of 2 as composite. Move on to the next unmarked number in the list, which is the 3. Now, mark all multiples of 3 as composite.
After completing this process for all numbers up to n, we will be left with only the prime numbers that remain unmarked.
Example
The following example illustrates the working of Sieve of Eratosthenes algorithm.
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
// method to find primes
void sieveOfEratos(int n) {
// initially assuming all values are prime
bool prm[n+1];
memset(prm, true, sizeof(prm));
// Loop over all numbers from 2 to sqrt(n)
for(int currPrm = 2; currPrm*currPrm <= n; currPrm++) {
// If current prime is still true, then it is a prime
if(prm[currPrm] == true) {
// Update all multiples of current prime
for(int i = currPrm*currPrm; i <= n; i += currPrm)
// Marking factor as not prime
prm[i] = false;
}
}
// to print the list of prime numbers
printf("List of first 50 prime numbers:
");
for(int i = 2; i <= n; i++) {
if(prm[i] == true)
printf("%d ", i);
}
}
int main() {
int lmt = 50;
sieveOfEratos(lmt);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
class SvEratos {
public:
// method to find primes
static void sieveOfEratos(int n) {
// initially assuming all values are prime
vector<bool> prm(n+1, true);
// Loop over all numbers from 2 to sqrt(n)
for(int currPrm = 2; currPrm*currPrm <= n; currPrm++) {
// If current prime is still true, then it is a prime
if(prm[currPrm] == true) {
// Update all multiples of current prime
for(int i = currPrm*currPrm; i <= n; i += currPrm)
// Marking factor as not prime
prm[i] = false;
}
}
// to print the list of prime numbers
cout << "List of first 50 prime numbers: " << endl;
for(int i = 2; i <= n; i++) {
if(prm[i] == true)
cout << i << " ";
}
cout << endl;
}
};
int main() {
int lmt = 50;
SvEratos::sieveOfEratos(lmt);
return 0;
}
public class SvEratos {
// method to find primes
public static void sieveOfEratos(int n) {
// initially assuming all values are prime
boolean prm[] = new boolean[n+1];
for(int i=0; i<=n; i++)
prm[i] = true;
// Loop over all numbers from 2 to sqrt(n)
for(int currPrm = 2; currPrm*currPrm <=n; currPrm++) {
// If current prime is still true, then it is a prime
if(prm[currPrm] == true) {
// Update all multiples of current prime
for(int i = currPrm*currPrm; i <= n; i += currPrm)
// Marking factor as not prime
prm[i] = false;
}
}
// to print the list of prime numbers
System.out.println("List of first 50 prime numbers: ");
for(int i = 2; i <= n; i++) {
if(prm[i] == true)
System.out.print(i + " ");
}
}
public static void main(String[] args) {
int lmt = 50;
sieveOfEratos(lmt);
}
}
def sieveOfEratos(n):
# initially assuming all values are prime
prm = [True for _ in range(n+1)]
# Loop over all numbers from 2 to sqrt(n)
currPrm = 2
while currPrm * currPrm <= n:
# If current prime is still true, then it is a prime
if prm[currPrm] == True:
# Update all multiples of current prime
for i in range(currPrm * currPrm, n+1, currPrm):
# Marking factor as not prime
prm[i] = False
currPrm += 1
# to print the list of prime numbers
print("List of first 50 prime numbers: ")
for i in range(2, n):
if prm[i] == True:
print(i, end=" ")
# test the function
lmt = 50
sieveOfEratos(lmt)
Output
List of first 50 prime numbers: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Binary Exponentiation Algorithm
The binary exponentiation algorithm is a procedure used to calculate the power of a given number. The naive approach to solve this type of problem i.e. np is by multiplying the number with itself p-1 times. However, it is a time-consuming process and not an efficient process.
Instead of the above approach, we can use the binary exponentiation algorithm which works as follows −
When the power of any given number is 0, the result will be 1.
If the number itself is even, use the following equation: ((n2)p/2), where n is the number and p is the power of that given number.
If the given number is odd, use the equation: (n*(n(p-1)/2)2).
Example
In this example, we will show how Binary Exponentiation algorithm works.
#include <stdio.h>
// function to calculate power
int bnryExp(int bs, int ex) {
int output = 1;
while (ex > 0) {
if (ex % 2 == 1) {
output *= bs;
}
// Square of base
bs *= bs;
// Divide power by 2
ex >>= 1;
}
// Return the result stored in output
return output;
}
int main() {
int bs = 3;
int ex = 6;
// Print the result
int result = bnryExp(bs, ex);
printf("The output of %d to the power %d is: %d
", bs, ex, result);
return 0;
}
#include <iostream>
using namespace std;
// method to calculate power
int bnryExp(int bs, int ex) {
// to store output
int output = 1;
while (ex > 0) {
if (ex % 2 == 1) {
output *= bs;
}
// Square of base
bs *= bs;
// Divide power by 2
ex /= 2;
}
// Return the result stored in output
return output;
}
int main() {
int bs = 3;
int ex = 6;
int result = bnryExp(bs, ex);
// Print the result
cout << "The output of " << bs << " to the power " << ex << " is: " << result << endl;
return 0;
}
public class Exponentiation {
// method to calculate power
public static int bnryExp(int bs, int ex) {
// to store output
int output = 1;
while (ex > 0) {
if (ex % 2 == 1) {
output *= bs;
}
// Square of base
bs *= bs;
// Divide power by 2
ex /= 2;
}
// Return the result stored in output
return output;
}
public static void main(String[] args) {
int bs = 3;
int ex = 6;
// Print the result
System.out.println("The output of " + bs + " to the power " + ex + " is: " + bnryExp(bs, ex));
}
}
# method to calculate power
def bnryExp(bs, ex):
# to store output
output = 1
while ex > 0:
if ex % 2 == 1:
output *= bs
bs *= bs
ex //= 2
return output
bs = 3
ex = 6
result = bnryExp(bs, ex)
print(f"The output of {bs} to the power {ex} is: {result}")
Output
The output of 3 to the power 6 is: 729
Modular Arithmetic
Modular arithmetic is a set of rules that is applicable in computing modulus expression. This concept becomes important when handling large numbers in competitive programming. The core idea of modular arithmetic is to find the remainder of a number upon division by another number.
Important properties of modulo are as follows −
(m mod n) mod n is equal to m mod n
(m*n) mod m is equal to 0
(P / Q) mod m ≠ ((P mod m) / (Q mod m)) mod m
(P + Q) mod m = ((P mod m) + (Q mod m)) mod m
(P – Q) mod m = ((P mod m) – (Q mod m) + m) mod m
(P * Q) mod m = ((P mod m) * (Q mod m)) mod m
Example
The following example demonstrates the working of modular arithmetic.
#include <stdio.h>
// function to perform addition
int modAddition(int valOne, int valTwo, int mod) {
// to handle negative values
if (valOne < 0) {
valOne = (valOne % mod + mod) % mod;
}
if (valTwo < 0) {
valTwo = (valTwo % mod + mod) % mod;
}
// addition
int sum = (valOne + valTwo) % mod;
// to ensure output is non-negative
return (sum + mod) % mod;
}
int main() {
int valOne = 22;
int valTwo = 26;
int mod = 5;
int output = modAddition(valOne, valTwo, mod);
printf("Modular addition of %d and %d modulo %d is: %d
", valOne, valTwo, mod, output);
return 0;
}
#include <iostream>
using namespace std;
int modAddition(int valOne, int valTwo, int mod) {
// to handle negative values
if (valOne < 0) {
valOne = (valOne % mod + mod) % mod;
}
if (valTwo < 0) {
valTwo = (valTwo % mod + mod) % mod;
}
// addition
int sum = (valOne + valTwo) % mod;
// to ensure the result is non-negative
return (sum + mod) % mod;
}
int main() {
int valOne = 22;
int valTwo = 26;
int mod = 5;
int output = modAddition(valOne, valTwo, mod);
cout << "Modular addition of " << valOne << " and " << valTwo << " modulo " << mod << " is: " << output << endl;
return 0;
}
public class ModAdd {
public static int modAddition(int valOne, int valTwo, int mod) {
// to handle negative values
if (valOne < 0) {
valOne = (valOne % mod + mod) % mod;
}
if (valTwo < 0) {
valTwo = (valTwo % mod + mod) % mod;
}
// addition
int sum = (valOne + valTwo) % mod;
// to ensure output is non-negative
return (sum + mod) % mod;
}
public static void main(String[] args) {
int valOne = 22;
int valTwo = 26;
int mod = 5;
int output = modAddition(valOne, valTwo, mod);
System.out.println("Modular addition of " + valOne + " and " + valTwo + " modulo " + mod + " is: " + output);
}
}
def mod_addition(val_one, val_two, mod):
# to handle negative values
if val_one < 0:
val_one = (val_one % mod + mod) % mod
if val_two < 0:
val_two = (val_two % mod + mod) % mod
# addition
sum = (val_one + val_two) % mod
# to ensure output is non-negative
return (sum + mod) % mod
val_one = 22
val_two = 26
mod = 5
output = mod_addition(val_one, val_two, mod)
print(f"Modular addition of {val_one} and {val_two} modulo {mod} is: {output}")
Output
Modular addition of 22 and 26 modulo 5 is: 3
