0

我想在 python 中实现 Karatsuba 乘法算法。但它不能完全工作。

该代码不适用于大于 999 的 x 或 y 值。对于低于 1000 的输入，程序显示正确的结果。它还在基本情况下显示正确的结果。

#Karatsuba method of multiplication.

f = int(input()) #Inputs
e = int(input())

def prod(x,y):
    r = str(x)
    t = str(y)
    lx = len(r)  #Calculation of Lengths
    ly = len(t)

    #Base Case

    if(lx == 1 or ly == 1):
        return x*y

    #Other Case

    else:
        o = lx//2
        p = ly//2

        a = x//(10*o)   #Calculation of a,b,c and d.
        b = x-(a*10*o)  #The Calculation is done by
        c = y//(10*p)   #calculating the length of x and y
        d = y-(c*10*p)  #and then dividing it by half.
                        #Then we just remove the half of the digits of the no.

        return (10**o)*(10**p)*prod(a,c)+(10**o)*prod(a,d)+(10**p)*prod(b,c)+prod(b,d)

print(prod(f,e))

我认为在计算 a、b、c 和 d 时存在一些错误。

4

1 回答 1

0 
a = x//(10**o)
b = x-(a*10**o)
c = y//(10**p)
d = y-(c*10**p)

你的意思是 10 的幂，但写的是 10 的乘积。

你应该训练自己找到这些类型的错误。有多种方法可以做到这一点：

  • 针对特定输入在纸上手动执行算法，然后单步执行您的代码并查看它是否匹配
  • 将代码缩减为子部分，并查看它们的预期值是否与生成的值匹配。在您的情况下，检查每次调用prod()预期输出是什么以及它产生什么，以找到产生错误结果的最小输入值。
  • 使用调试器单步执行代码。在每一行之前，考虑结果应该是什么，然后查看该行是否产生了该结果。
于 2019-06-27T12:08:16.717 回答