除法与GCD算法的相关分析

学习算法三个要素：

1、验证算法的正确性
2、分析算法的效率
3、如何提高算法的效率

以下是两个算除法的“玩具”算法，请验证其正确性，分析它们的效率并进行对比，并思考是否可以进一步提高除法的效率。最后这个问题不容易。

def QuoRem(a, b):
    q, r = 0, 0
    while(a >= b):
        a, q = a - b, q + 1
    r = a
    return q, r

def BinaryQuoRem(a, b):
    if(a == 0):
        return 0, 0
    q, r = BinaryQuoRem(a // 2, b)
    q, r = 2 * q, 2 * r
    if(a & 1): #if a is an odd number
        r = r + 1
    if(r >= b):
        r, q = r - b, q + 1
    return q, r

GCD 与Binary GCD的对比

为什么需要Binary GCD？
为什么看上去Binary GCD更高效？
但是，Binary GCD真的更高效吗？为什么是，为什么不是？
请分析下面这两个算法，并回答以上问题。

# Function to implement Euclidean Algorithm
def gcd(a, b):
    while(b):
        a, b = b, a % b
    return a

# Function to implement Stein's Algorithm
def binary_gcd( a, b) :

    # GCD(0, b) == b; GCD(a, 0) == a,
    # GCD(0, 0) == 0
    if (a == 0) :
        return b

    if (b == 0) :
        return a

    # Finding K, where K is the greatest
    # power of 2 that divides both a and b.
    k = 0

    while(((a | b) & 1) == 0) :
        a = a >> 1
        b = b >> 1
        k = k + 1

    # Dividing a by 2 until a becomes odd
    while ((a & 1) == 0) :
        a = a >> 1

    # From here on, 'a' is always odd.
    while(b != 0) :

        # If b is even, remove all factor of
        # 2 in b
        while ((b & 1) == 0) :
            b = b >> 1

        # Now a and b are both odd. Swap if
        # necessary so a <= b, then set
        # b = b - a (which is even).
        if (a > b) :

            # Swap u and v.
            a, b = b, a

        b = (b - a)

    # restore common factors of 2
    return (a << k)

总结

算法分析实在是太难了！

参考文献

1、对Binary GCD的分析
2、Recursive Binary GCD
3、快速乘法及其应用

---

2018.0518