s = '''
import fractions
a = 10
b = 12

def b_gcd(m, n):
    fact = 1
     
    while m > 1 and n > 1 and m != n:
     
        om, on = m & 1, n & 1
         
        if om and on:
            m, n = abs(m - n)>>1, min(m, n)
         
        elif not (om or on):
            fact, m, n = fact<<1, m>>1, n>>1
         
        else:
            m, n = (m>>1, n) if on else (m, n>>1)
     
    m, n = (m, n) if n > m else (n, m)
    return (m or n)<<(fact - 1)

def gcd3(m, n):
    while m != 0 and n != 0:
        if m > n:
            m = m % n
        else:
            n = n % m
    return (m + n)


def gcd2(m, n):
    factor = 1

    while m > 1 and n > 1:

        if m % 2 == 0 and n % 2 == 0:
            factor *= 2
            m /= 2
            n /= 2
            continue
        elif m % 2 != 0 and n % 2 != 0:
            m, n = abs(m - n) / 2, min(m, n)
            continue

        if m % 2 == 0:
            m /= 2

        if n % 2 == 0:
            n /= 2

    if m == 0 or n == 0:
        out = m + n
    elif n == m:
        out = n
    elif m == 1 or n == 1:
        out = 1

    return factor * out


def gcd(m, n):
    if m == 0:
        return n

    if n == 0:
        return m

    if m == n:
        return n

    if m == 1 or n == 1:
        return 1

    if m % 2 == 0 and n % 2 == 0:
        return 2 * gcd(m / 2, n / 2)

    if m % 2 == 0 and n % 2 != 0:
        return gcd(m / 2, n)

    if n % 2 == 0 and m % 2 != 0:
        return gcd(m, n / 2)

    if m % 2 != 0 and n % 2 != 0:
        if n > m:
            return gcd((n-m)/2, m)

        else:
            return gcd((m-n)/2, n)
'''
import random
import timeit
import fractions

# for test in range(100):
#     a, b = random.randint(0, 100), random.randint(0, 100)
#     fa = gcd(a, b)
#     fb = gcd2(a, b)
#     assert fa == fb, 'Not ok'

number = 10 ** 5
print timeit.timeit('gcd(a, b)', setup=s, number=number)
print timeit.timeit('gcd2(a, b)', setup=s, number=number)
print timeit.timeit('gcd3(a, b)', setup=s, number=number)
print timeit.timeit('b_gcd(a, b)', setup=s, number=number)
print timeit.timeit('fractions.gcd(a, b)', setup=s, number=number)
print 'ok'