Python中的Karatsuba算法

Question

我用Python实现了一个Karatsuba算法，但它并没有给出确切的答案。

def karatsuba(x, y):
    if x < 10 or y < 10:
        return x*y

    #making the two numbers strings here
    str_x = str(x)
    str_y = str(y)

    #finding the mid point for each number here
    n = max(len(str(x)), len(str(y)))
    n_2 = int(n / 2)

    #higher bits of each number
    x_h = int(str_x[:n_2])
    y_h = int(str_y[:n_2])

    #lower bits for each number here
    x_l = int(str_x[n_2:])
    y_l = int(str_y[n_2:])

    a = karatsuba(x_h, y_h)
    d = karatsuba(x_l, y_l)
    e = karatsuba(x_h + x_l, y_h + y_l) - a - d

    return a*10**len(str_x) + e*10**(len(str_x) // 2) + d


result = karatsuba(1234, 8765)
print(result)

我认为这是因为我取整数值而忽略浮点值的小数。

当我运行上面的程序时，我的答案是10,402,010，而实际答案是10,816,010。

我怎样才能改善这一点？

Answer 1

代码

中的错误

1. 当您拆分str_x[:n_2]和str_y[:n_2]时，您从每个数字中最重要的部分获取相同数量的数字。相反，您需要从每个数字中最不重要的部分获取相同数量的数字。

例如，karatsuba(12 + 34, 87 + 65)的交叉乘法步骤出错：

得到x = 46，y = 152，n_2 =1，str_x[:n_2] = '4‘和str_y[:n_2] = '1’。这些都不会被相同的金额抵消！

相反，你可以设置

#higher bits of each number
x_h = int(str_x[:-n_2])
y_h = int(str_y[:-n_2])

#lower bits for each number here
x_l = int(str_x[-n_2:])
y_l = int(str_y[-n_2:])

负指数从结尾算起，这正是你想要的，这样你就可以从每个人中抽出相同数量的10倍的幂。然后str_x[:-n_2] = str_x[:-1] =除最后一个n_2 = x的1位数字为4，而str_y[:-n_2] = str_x[:-1] =除最后一个n_2 =1位数字的x为15。

1. 不管有没有上述修复，当两个数字都> 10并且其中一个数字是另一个数字的两倍(或更多)时，您的代码就会崩溃。然后，其中一个切片将是空字符串，int('')抛出一个错误，而不是(正如您希望的那样)返回0。

解决这一问题的一个快速方法是将较高部分和较低部分分别设置为一个函数，并检查空字符串。或者，您可以在karatsuba中有一个特例，当n_2 >= min(...)

1. 最后，返回计算中有一个错误。您需要的不是len(str_x)，而是2 * n_2，而不是len(str_x) // 2，而是n_2。

对错误

以外的其他问题的一些快速评论

使用str(x)并不是很有效，并且在一种高效的乘法方法的实现中做了很多额外的工作。不过，为了降低算法的基本思想，一开始没问题，我不会抱怨太多。

但是，您至少应该知道，更好的方法是将数字分割为基2中的两个部分，并使用位字符串操作。这将是一个很好的后续练习。具体来说，x >> n与x // 2**n相同，x << n与x * 2**n相同，这些操作比基10操作高效得多。