python - 如何改进我的 karatsuba Logic 以使我的代码正常工作？

Question

无法让我的 Karatsuba 算法正常工作。我的代码中有一个无限循环。我认为问题开始于：

q = str(int(c) + int(d))

因为 None 是返回值。为什么没有返回？

到目前为止，我的调查使我得出结论，我的无限循环是：

pq = Karatsuba(p, q)

重新调整我的代码，但到目前为止没有任何效果。

def Karatsuba( x, y):

    '''
    Input: Two n-digit positive integers. N must be a power of two.

    Output: The product of x and y.
    '''
    if len(x) == 1 and len(y) == 1:

        return int(x) * int(y)

    else:

        split = len(x) // 2

        a = x[:split]
        b = x[split:]
        c = y[:split]
        d = y[split:]

        ac = Karatsuba(a, c)
        bd = Karatsuba(b, d)

        p = str(int(a) + int(b))
        q = str(int(c) + int(d))

        pq = Karatsuba(p, q)

        adbc = pq - ac - bd


        return 10**len(x) * ac + (10**split) * adbc + bd

print(Karatsuba('1234', '5678'))

产生的答案应该是 7006652

标签： pythonpython-3.xalgorithmlogic