Naive Algorithm
Function NaiveGCD(a, b)
best <- 0
for d from 1 to a+b:
if d|a and d|b:
best <- d
return best
- Runtime approximately a+b
- Very slow for 20 digit numbers
Python Implementation
def gcd(m, n):
gc = 0
for i in range(1, m+n):
if m % i == 0 and n % i == 0:
gc = i
return gc
default_a = 3918848
default_b = 1653264
a = input("Enter a: [%s]" % default_a)
b = input("Enter b: [%s]" % default_b)
a = a or default_a
b = b or default_b
g = gcd(int(a), int(b))
print("GCD is: ", g)
Euclidean Algorithm (Better Approach)
Key Lemma:
Let a’ be the remainder when a is divided by b, then,
gcd(a,b) = gcd(a’,b) = gcd(b,a’)
Function EuclidGCD(a,b) if b = 0: return a; a' <- remainder when a is divided by b return EuclidGCD(b, a')
Runtime Analysis
- Each step reduces the size of numbers by about a factor of 2.
- Takes about log(ab) steps.
- GCDs of 100 digit numbers takes about 600 steps.
- Each step a single division.
Example
gcd(3918848, 1653264)
= gcd(1653264, 612320)
= gcd(612320, 428624)
= gcd(428624, 183696)
= gcd(183696, 61232)
= gcd(61232, 0)
= 61232
As we can see new algorithm took around 6 steps, however previous algorithm would have checked around 5 million different combinations.
Python Implementation
def euclid_gcd(m, n): """Calculate the Greatest Common Divisor of a and b. Unless b==0, the result will have the same sign as b (so that when b is divided by it, the result comes out positive). """ while n: m, n = n, m%n return m default_a = 3918848 default_b = 1653264 a = input("Enter a: [%s]" % default_a) b = input("Enter b: [%s]" % default_b) a = a or default_a b = b or default_b g = euclid_gcd(int(a), int(b)) print("GCD is: ", g)