0

我正在做斯坦福的算法 MOOC 并且被 Karatsuba 乘法算法编程作业卡住了。
Karatsuba 乘法只是一种用于两个整数相乘的算法，它比通常的乘法渐进地快。

限制

  • 我限制自己只使用一位数的乘法和填充数字（最后加零，即乘以 10 到某个幂），所以有 3 个基本情况
  • 我还决定将数字转换为字符串并取多个数字，而不是将其除以 10 的幂，但我尝试了另一种方法，它没有帮助
  • 我还决定概括该算法，即不要假设 number1 和 number2 具有相似的长度，因此我同时使用 n1 和 n2（参见代码）
  • 由于以上几点，我也决定不使用高斯的技巧

我知道，这些限制可能看起来毫无意义，但我将它用作编程练习而不是一些实际的解决方案，因此我主要感兴趣的是发现我的错误而不是找到一些“更简单的解决方案”。

这是我的代码：

    def karatsuba(number1, number2):
        n1 = len(str(number1)) # number of digits in the first number
        n2 = len(str(number2)) # number of digits in the second number

        if n1 == 1 and n2 == 1: # base case number 1 - both numbers are single-digit
            kara = number1*number2
            return kara

        elif n1 == 1: # base case number 2 - only one number is single-digit
            c = int(str(number2)[:(n2//2)])
            d = int(str(number2)[(n2//2):])
            kara = 10**((n2+1)//2)*c*number2 + d*number2
            return kara

        elif n2 == 1: # base case number 3 - only one number is single digit
            a = int(str(number1)[:(n1//2)])
            b = int(str(number1)[(n1//2):])
            kara = 10**((n2+1)//2)*a*number2 + b*number2
            return kara

        elif n1 != 1 and n2 != 1: # loop
            a = int(str(number1)[:(n1 // 2)])
            b = int(str(number1)[(n1 // 2):])
            c = int(str(number2)[:(n2 // 2)])
            d = int(str(number2)[(n2 // 2):])
            z1 = karatsuba(a, c)
            z2 = karatsuba(a, d)
            z3 = karatsuba(b, c)
            z4 = karatsuba(b, d)
            kara = 10**((n1+1)//2+(n2+1)//2)*z1 + 10**((n1+1)//2)*z2 + 10**((n2+1)//2)*z3 + z4
            return kara
4

2 回答 2

1

这不是 Karatzuba 算法。Karatzuba 的要点是只进行 3 次递归调用；你做了其中的4个。在您的符号中，递归调用应该是

karatzuba(a, c)
karatzuba(b, d)
karatzuba(a + b, c + d)

除此之外，基本案例 2 存在一个问题：number1根本不参与其中。

于 2020-06-26T22:10:52.190 回答
1

如果您还没有，这些是一些需要纠正的错误。

kara = 10**((n2+1)//2)*c*number1 + d*number1 #in base case 2 

kara = 10**((n1+1)//2)*a*number2 + b*number2 #in base case 3. your code has n2+1

传统的 Karatsuba 有 3 次递归。但我明白你为什么要进行 4 次递归。不能说哪个更快。

您在上面在评论中给出的示例的工作代码

def karatsuba(number1, number2):
    n1 = len(str(number1)) # number of digits in the first number
    n2 = len(str(number2)) # number of digits in the second number

    if n1 == 1 and n2 == 1: # base case number 1 - both numbers are single-digit
        kara = number1*number2
        return kara

    elif n1 == 1: # base case number 2 - only one number is single-digit
        c = int(str(number2)[:(n2//2)])
        d = int(str(number2)[(n2//2):])
        kara = 10**((n2+1)//2)*c*number1 + d*number1 #a mistake here
        return kara

    elif n2 == 1: # base case number 3 - only one number is single digit
        a = int(str(number1)[:(n1//2)])
        b = int(str(number1)[(n1//2):])
        kara = 10**((n1+1)//2)*a*number2 + b*number2 #a mistake here
        return kara

    elif n1 != 1 and n2 != 1: # loop
        a = int(str(number1)[:(n1 // 2)])
        b = int(str(number1)[(n1 // 2):])
        c = int(str(number2)[:(n2 // 2)])
        d = int(str(number2)[(n2 // 2):])
        z1 = karatsuba(a, c) 
        z2 = karatsuba(a, d) 
        z3 = karatsuba(b, c)
        z4 = karatsuba(b, d) 
        kara = 10**((n1+1)//2+(n2+1)//2)*z1 + 10**((n1+1)//2)*z2 + 10**((n2+1)//2)*z3 + z4
        return kara
num1 = 3141592653589793238462643383279502884197169399375105820974944592
num2 = 2718281828459045235360287471352662497757247093699959574966967627
k_res = karatsuba(num1,num2)
ac_res = num1*num2
print(k_res)
print(ac_res)
assert k_res==ac_res
于 2020-06-27T11:51:41.427 回答