python - 编码 Karatsuba 乘法

Question

如果任何一个数字的长度都是偶数，我下面的代码似乎运行良好，但如果两个数字的长度都是奇数（如图片中所示），它会输出错误的结果。我不知道哪里出了问题或如何解决它。

def karatsubaMulti(num1, num2):
    len1 = len(str(num1))
    len2 = len(str(num2))

    if len1==1 or len2==1:
        return num1*num2

    else:
        maxLen = max(len1, len2)

        if maxLen > len1:
            a=0
            b=num1
        else:
            a = num1 // pow(10, maxLen//2)
            b = num1 %  pow(10, maxLen//2)

        if maxLen > len2:
            c=0
            d=num2
        else:
            c = num2 // pow(10, maxLen//2)
            d = num2 % pow(10, maxLen//2)
        z1 = karatsubaMulti(a, c)
        z2 = karatsubaMulti(b, d)
        z3 = karatsubaMulti(a+b, c+d)
        return z1 * pow(10, maxLen) + (z3-z1-z2) * pow(10, maxLen//2) + z2
x = 171
y = 571

xy1 = karatsubaMulti(x, y)

print(xy1)

Answer 1

仔细查看公式，将其与正确的公式进行比较，您会发现 的平方pow(10, maxLen//2)不是pow(10, maxLen)。