---
title: WDI 5.3
---

def gcd(n, m):
    multiplier = 1

    while m > 0:
        if n < m:
            k = m
            m = n
            n = k
        ilenp = n % 2 + m % 2
        if ilenp == 2:
            n = n - m
        elif ilenp == 0:
            n /= 2
            m /= 2
            multiplier *= 2
        elif n % 2 == 0:
            n /= 2
        else:
            m /= 2

    return n * multiplier


# def gcdr(n, m):
#     if m == 0:
#         return n
#     if n < m:
#         return gcdr(m, n)
#     ilenp = n % 2 + m % 2
#     if ilenp == 2:
#         return gcd(n - m, m)
#     if ilenp == 0:
#         return 2 * gcd(n / 2, m / 2)
#     if n % 2 == 0:
#         return gcd(n / 2, m)
#     else:
#         return gcd(n, m / 2)


print('non-recursive', gcd(1280, 280))
# print('non-recursive', gcdr(1280, 280))