greatest common divisor euclidean Algorithm
The greatest common divisor (GCD) Euclidean algorithm is an ancient and efficient method to determine the greatest common divisor of two integers. The greatest common divisor, also known as the highest common factor, is the largest positive integer that divides both numbers without leaving a remainder. The algorithm was initially described by the Greek mathematician Euclid in his book "Elements" around 300 BC. Although he developed the algorithm primarily for geometric purposes, it has since become a fundamental tool in number theory and modern computer science.
The Euclidean algorithm is based on the simple observation that the GCD of two numbers remains unchanged if the larger number is replaced by the difference between the two numbers. The algorithm works by repeatedly applying this observation until both numbers become equal, which will then be the GCD of the original numbers. The algorithm can be implemented efficiently using either a recursive or iterative approach. One of the significant advantages of the Euclidean algorithm is its efficiency - the number of steps it takes to compute the GCD is logarithmic in the size of the input numbers. This property has made it an essential component in various applications, such as cryptography, computer algebra systems, and rational number arithmetic.
#include <cmath>
#include <iostream>
#include <stdexcept>
// will find the greatest common denominator of two ints integers
// Euclidean algorithm can be found here
// https://en.wikipedia.org/wiki/Euclidean_algorithm
int gcd(int num1, int num2) {
if (num1 <= 0 | num2 <= 0) {
throw std::domain_error("Euclidean algorithm domain is for ints > 0");
}
if (num1 == num2) {
return num1;
}
int base_num = 0;
int previous_remainder = 1;
if (num1 > num2) {
base_num = num1;
previous_remainder = num2;
} else {
base_num = num2;
previous_remainder = num1;
}
while ((base_num % previous_remainder) != 0) {
int old_base = base_num;
base_num = previous_remainder;
previous_remainder = old_base % previous_remainder;
}
return previous_remainder;
}
int main() {
std::cout << "gcd of 120,7 is " << (gcd(120, 7)) << std::endl;
try {
std::cout << "gcd of -120,10 is " << gcd(-120, 10) << std::endl;
} catch (const std::domain_error &e) {
std::cout << "Error handling was successful" << std::endl;
}
std::cout << "gcd of 312,221 is " << (gcd(312, 221)) << std::endl;
std::cout << "gcd of 289,204 is " << (gcd(289, 204)) << std::endl;
return 0;
}
