Karatsuba 递归代码无法正常工作

Question

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

对于输入小于 1000 的大于 999.For 的 x 或 y 值，该代码无效，程序显示正确 result.It 也显示基本情况的正确结果。

#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的计算有一些bug

Answer 1

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

你的意思是10的次方，但是写的是10乘以。

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

针对特定输入在纸上手动执行算法，然后单步执行代码并查看它是否匹配
将代码减少到 sub-portions 并查看它们的预期值是否与产生的值匹配。在你的情况下，检查每次调用 prod() 预期的输出是什么以及它产生了什么，以找到产生错误结果的最小输入值。
使用调试器单步执行代码。在每一行之前，想想结果应该是什么，然后看看该行是否产生了那个结果。

Karatsuba 递归代码无法正常工作

Karatsuba recursive code is not working correctly

recursion

python-3.x

karatsuba