algorithm - 在不使用 / 或 * 运算符的情况下执行除法的最快方法任何其他解决方案

Question

我正在关注 Skiena 的算法书。在第 1 章中，给出了不使用 / 或 * 运算符来除实数的问题。我在python中实现了这样的：

def main(dividend, divisor ):
    print "dividend : ",dividend
    print "divisor : ", divisor
    if dividend<divisor:
        print "dividend has to be greater than divisor"
        return;
    quotient=0
    sum=0
    while sum<dividend:
        sum = sum+divisor
        print "sum : ",sum
        quotient = quotient+1
        if sum>dividend:
            remainder = dividend-(sum-divisor)
            quotient=quotient-1
            print "remainder : ", remainder
    print "quotient :", quotient





    if __name__ == "__main__":
        # pass any two real number as dividend and divisor
        main(29, 3)

该问题还指出，您必须“找到最快的方法”。有没有其他方法可以更快地解决问题？

Answer 1

我不会为你编写代码，但一种快速的方法是使用 2 的幂并且仅使用加法和减法运算符。让我们以 973 / 47 为例。首先建立一个 2 倍除数的幂表；你可以通过简单的添加来做到这一点：

1:  47
2:  94
4:  188
8:  376
16: 752
32: 1504

每个 2 的幂只是添加到自身的前一个 2 的幂。当 2 的幂超过股息时停止。现在向后工作，如果它小于剩余的股息，则减去 2 的幂：

16: 973 - 752 = 221
4:  221 - 188 = 33

所以商是 16 + 4 = 20，余数是 33。

该算法类似于我在博客中讨论的乘法农民算法。