Karatsuba算法不正确的结果

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

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，这肯定是错误的...

来源

2013-04-07 kun

是完全坦白，这是一些我见过的最奇怪的Python代码的。为什么'f'如此冗长（而不仅仅是'int（x）％2'）？你为什么要用'str'而不是'int'来传递（你可以用'math.log10'来确定一个以10为底的数字的长度）？你为什么使用'x .__ len __（）'而不是简单得多的'len（x）'？你为什么要做一个包含两个整数的'int_buff'，而不是仅仅两个新的变量？这一切都非常和谐！ – nneonneo 2013-04-07 08:18:28

真的..我想这是因为我每次打开这个代码是在凌晨3:00 .. – kun 2013-04-07 08:37:01

我认为你应该重写算法使用基地'2'而不是基地'10'并避免字符串。请记住，计算机中的数字以基数2表示。您可以用“10 **度”替换乘法。 – Bakuriu 2013-04-07 11:59:58

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

我无法抗拒它的重构...一点点。我使用了wiki上定义的名称。用任意的基础来实现它会很简单，但为了简单起见，我坚持使用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

来源

2013-04-07 19:20:30 Richard

这个人很酷 – kun 2013-04-07 22:32:55

Karatsuba算法不正确的结果

回答

相关问题