euclidean gcd Algorithm
The Euclidean Algorithm is an ancient mathematical technique used to find the greatest common divisor (GCD) of two given integers. The GCD of two integers is the largest positive integer that divides both the numbers without leaving a remainder. This algorithm, attributed to the Greek mathematician Euclid, is based on the principle that the GCD of two numbers remains the same if the larger number is replaced by the difference between the two numbers. The algorithm is an iterative process that reduces the problem of finding the GCD of two numbers to a series of smaller instances of the same problem, eventually arriving at the GCD.
To implement the Euclidean Algorithm, one starts with two integers, a and b, where a is larger than b. The algorithm proceeds by repeatedly subtracting b from a until the remainder is smaller than b. At this point, the roles of a and b are swapped, and the process is repeated until one of the numbers becomes zero. The other number is then the GCD of the original two integers. In practice, this algorithm is often implemented using the modulo operation, which calculates the remainder after division, making it more efficient than subtraction. This optimized version is known as the "Division-based Euclidean Algorithm," which divides the larger number by the smaller number and replaces the larger number with the remainder until the remainder becomes zero, and the GCD is found.
""" https://en.wikipedia.org/wiki/Euclidean_algorithm """
def euclidean_gcd(a: int, b: int) -> int:
"""
Examples:
>>> euclidean_gcd(3, 5)
1
>>> euclidean_gcd(6, 3)
3
"""
while b:
a, b = b, a % b
return a
def euclidean_gcd_recursive(a: int, b: int) -> int:
"""
Recursive method for euclicedan gcd algorithm
Examples:
>>> euclidean_gcd_recursive(3, 5)
1
>>> euclidean_gcd_recursive(6, 3)
3
"""
return a if b == 0 else euclidean_gcd_recursive(b, a % b)
def main():
print(f"euclidean_gcd(3, 5) = {euclidean_gcd(3, 5)}")
print(f"euclidean_gcd(5, 3) = {euclidean_gcd(5, 3)}")
print(f"euclidean_gcd(1, 3) = {euclidean_gcd(1, 3)}")
print(f"euclidean_gcd(3, 6) = {euclidean_gcd(3, 6)}")
print(f"euclidean_gcd(6, 3) = {euclidean_gcd(6, 3)}")
print(f"euclidean_gcd_recursive(3, 5) = {euclidean_gcd_recursive(3, 5)}")
print(f"euclidean_gcd_recursive(5, 3) = {euclidean_gcd_recursive(5, 3)}")
print(f"euclidean_gcd_recursive(1, 3) = {euclidean_gcd_recursive(1, 3)}")
print(f"euclidean_gcd_recursive(3, 6) = {euclidean_gcd_recursive(3, 6)}")
print(f"euclidean_gcd_recursive(6, 3) = {euclidean_gcd_recursive(6, 3)}")
if __name__ == "__main__":
main()
