GCD Of Two Numbers

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)

Leave a Reply