gcd (Greatest Common Divisor)

Tags: [math], [gcd], [Euclidean's_algorithm]

Given two integers, how to calculate the gcd (Greatest Common Divisor) of them.

Solution: Euclidean' algorithm

def get_gcd(a, b):
    a = abs(a)
    b = abs(b)

    if b == 0:
        return a

    r = a % b

    # base case
    if r == 0:
        return b

    return get_gcd(b, r)

if __name__ == '__main__':
    print 'Program is working'

    # a = 10
    # b = 25

    a = -5
    b = 0

    gcd = get_gcd(a, b)
    print gcd

    print 'Program is end'

Note:

  • gcd(a, b), a and b can be negative, but gcd must be a positive integer. "In mathematics, the greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that is a divisor of both numbers. For example, the GCD of 8 and 12 is 4", reference: https://en.wikipedia.org/wiki/Greatest_common_divisor

  • Explanation of the base case: If the remainder has already been 0, we can just return the denominator (除数).

  • Time complexity = O(lgb). Reference: http://www.cnblogs.com/johnnyflute/p/3738213.html

  • For this algorithm, it doesn't matter whether a is smaller than b. Think if a < b, r = a % b, so r will equal to a, and the next round is gcd(b, r), because r = a, so the next round become gcd(b, a), the mod operation help us to put the bigger element to the left side, and smaller element to the right side.

Euclidean Algorithm:

  • gcd(a, b) = gcd(b, a mod b)

  • Knowledge: If two numbers are co-prime, the gcd of these two numbers is 1.

  • Knowledge: c = gcd(a, b), a = m*c, b = n*c, so m and n are co-prime.

Start proof:

  1. Given two integers, a and b, and c = gcd(a, b), a = k * b + r, r = a % b
  2. a = m*c, b = n*c, m and n are integers.
  3. Because a = k*b + r, so r = a - k*b
  4. r = m*c - k*n*c, r = (m - k*n)*c.
  5. Look at r = (m - k*n)*c, and b = n*c, we know m, n, k are integers, so (m - k*n) is integer, so r = some_int_1 * c, b = some_int_2 * c.
  6. If some_int_1 and some_int_2 are co-prime, we can get gcd(b, r) = c.
  7. So now our goal is to prove (m - k*n) and n are co-prime.
  8. We can use “proof by contradiction”(反证法)

  9. Contradiction Assumption: (m - k*n) and n are not co-prime.

  10. So there must exist a common divisor which is greater than 1, between (m - k*n) and n. We assume this common divisor is D, D > 1.

  11. So (m - k*n) = D*x, n = D*y.

  12. m = D*x - k*n, m = D*x - k*D*y, m = (x - k*y)*D.

  13. Because a = m*c, so a = (x - k*y)*D*c.

  14. Because b = n*c, so b = D*y*c, b = y*D*c.

  15. Look, a = (x - k*y)*D*c, and b = y*D*c, because x, y, k are integers, so (x - k*y) is an integer. So now a = some__int__1 * D*c, and b = some__int_2 * D*c, which means (D*c) is a common divisor between a and b, and we know D > 1, so (D*c) > c, so c is not the gcd of a and b, which contradict the fact that c = gcd(a, b). So our Contradiction assumption is wrong. So we proved that (m - k*n) and n are co-prime. Co-prime means the gcd between (m - k*n) and n is 1, which means we cannot extract a common divisor which is greater than 1, which means, if r = (m - k*n)*c, b = n*c, we cannot extract something from (m - k*n) and n to combine the c to make a common divisor of r and b greater than c, which means c is the greatest common divisor of r and b.

  16. Because b = n*c, r = (m - k*n)*c, and n and (m - k*n) are co-prime. So c is gcd of b and r, so c = gcd(b, r).

  17. Because c = gcd(a, b), c = gcd(b, r), so gcd(a, b) = gcd(b, r), r = a % b.

Explanation of time complexity = O(lgb):

  • The main idea is that we collect the generated numbers during the iterations, when we calculate gcd (during the recursion). gcd(a, b) => gcd(b, (a mod b)) => gcd ((a mod b), (b mod (a mod b))) ==> ...

  • For example, gcd(25, 10) ==> gcd(10, 5) ==> gcd(5, 0), because the base case is checking b is 0 or not, so we can collect all 'b's, and list them as a sequence:10==>5==>0, and we can reverse them as: [0, 5, 10]. We can compare this sequence with Fibonacci sequence. (Personally I think, we can compare this 'gcd sequence' with any similar sequence, but here we are familiar with the Fibonacci sequence, so here we use Fibonacci sequence).

  • The Fibonacci sequence is [1, 1, 2, 3, 5, 8, 13, 21, 36, 57, ...]. We can see the 'gcd sequence' is climbing up faster than Fibonacci sequence.

  • For Fibonacci sequence, we assume it takes n steps from 1 to get Fn. And we know the growth of Fibonacci sequence follows exponential form. So Fn is about equal to 2^n, so n is about equal to lg(Fn), which means Fibonacci sequence from 1 to Fn, takes about lg(Fn) iterations.

  • We know the 'gcd sequence' climbs faster than Fibonacci sequence (exponential form), which means if 'gcd sequence' wants to climb from 0 to b, the number of steps it takes should be less than lg(b). So the time complexity of gcd = O(lgb).

Explanation of time complexity = O(lgb), follow-up:

  • We can use the exponential sequence to compare with the 'gcd sequence'.
  • The exponential sequence is [2^0, 2^1, 2^2, 2^3, 2^4, ...], which is [1, 2, 4, 8, 16, ...]
  • The 'gcd sequence' is [0, 5, 10, ...]
  • Compare the exponential sequence with the 'gcd sequence', we can see the 'gcd sequence' climbs up faster than exponential sequence.
  • For the exponential sequence, we assume it take n times iterations, from 1 to Fn, (each time curr = prev * 2). 2^n = Fn, so n = lg(Fn).
  • So for ''gcd sequence', we assume it take n times iterations, from 0 to Fn, so the times of iterations should be less than n, which means the times of iterations should be less than lg(Fn), here Fn is 'b' (Because for the 'gcd sequence', we are watching b (b == 0 is the base case of the recursion)), so the times of the iterations is less than lg(b), so the time complexity = O(lgb).

results matching ""

    No results matching ""