python - Karatsuba 算法不正确的结果

Question

我只是简单地遵循了 wiki 上的伪代码 http://en.wikipedia.org/wiki/Karatsuba_algorithm但是这个实现的结果很不稳定。它有时会起作用，但以防 100*100。它确实失败了。我在这里错过了什么？请看一下。

from math import *
f = lambda x: (int(x) & 1 and True) and 1
def fast_multiply( x = "100", y = "100"):
    print "input "+x+" | "+y
    int_buff = map( int, [x, y])
    if int_buff[0] < 10 or int_buff[1] < 10:
        #print "lol"
        return int_buff[0]*int_buff[1]

    degree = max( x.__len__(), y.__len__())

    higher_x, lower_x = x[ : int( ceil( len(x) / 2.0))], x[ len(x)/2 +f(len(x)):]
    higher_y, lower_y = y[ : int( ceil( len(y) / 2.0))], y[ len(y)/2 +f(len(y)):]
    #print lower_x+" & "+lower_y
    z0 = fast_multiply(lower_x, lower_y) #z0 = 0
    z1 = fast_multiply(str(int(lower_x)+int(higher_x)), str(int(lower_y)+int(higher_y)))
    z2 = fast_multiply(higher_x, higher_y)
    print "debug "+str(z0)+" "+str(z1)+" "+str(z2)
    return z2*(10**degree) + (z1-z2-z0)*(10**(degree/2))+z0




if __name__ == '__main__':
    print fast_multiply()

我注意到在这种情况下 100*100 z2 将是 100，这是正确的。这给出了 z2*(10**3)=100000 这绝对是错误的...

Answer 1

您使用的伪代码是错误的。问题出在 z2*(10**degree) .您应该将基数提高到 2*m其中 m是你打算用 int( ceil(len(x) / 2.0)) 计算的( len(x) 和 len(y) 应该都是 degree )。

我忍不住重构它……一点点。我使用了维基上定义中的名称。用任意基数实现它会很简单，但为简单起见，我坚持使用 10。

def kmult(x, y):
    if min(x, y) < 10:
        return x * y

    m = half_ceil(degree(max(x, y)))

    x1, x0 = decompose(x, m)
    y1, y0 = decompose(y, m)

    z2 = kmult(x1, y1)
    z0 = kmult(x0, y0)
    z1 = kmult(x1 + x0, y1 + y0) - z2 - z0

    xy = z2 * 10**(2*m)  +  z1 * 10**m  +  z0
    return xy


def decompose(x, m):
    return x // 10 ** m, x % 10 ** m

def degree(x):
    return len(str(x))

def half_ceil(n):
    return n // 2 + (n & 1)

测试:

print kmult(100, 100)

def test_kmult(r):
    for x, y in [(a, b) for b in range(r+1) for a in range(r+1)]:
        if kmult(x, y) != x * y:
            print('fail')
            break
    else:
        print('success')


test_kmult(100)

结果:

10000
success