我想知道有关Katatsuba算法的问题。当你申请Karatsuba你基本上做到每循环其中的一个运行3次乘法（假设ab和cd与数字2位数分别为a, b, c and d）：
X = bd
Y = ac
Z = (a+c)(c+d)
然后我们要寻找的总和是：
bd = X
ac = Y
(bc + ad) = Z - X - Y
我的问题是：假设我们有两个3位数字：abc, def。我发现我们只需执行5次乘法即可。我也找到了这个Toom-3算法，但是它使用了我无法完全理解的多项式。有人可以写下这些乘法以及如何计算有趣的总和bd + ae, ce+ bf, cd + be + af
基本思想是：数字237是在点x = 10求出的多项式p（x）= 2x 2 + 3x + 7。因此，我们可以想到每个与一个多项式相对应的整数，该多项式的系数是数字的位数。当我们在x = 10处评估多项式时，我们得到了数字。
有趣的是，要完全指定2次多项式，我们仅需要3个不同点的值即可。我们需要5个值来完全指定4级的多项式。
因此，如果我们想将两个3位数相乘，可以通过以下方式进行：
Karatsuba乘法的工作方式相同，只是我们只需要3个不同的点。而不是在10处，我们在0、1和“无穷大”处评估多项式，这将给我们带来乘积b,a+b,a，d,d+c,c然后相乘得出您的X,Z,Y。
现在，将所有内容写成abc且def相当复杂。在Wikipedia文章中，它实际上做得很好：
c,a+b+c,a-b+c,4a+2b+c,a第一个数字。X = cf Y = (a+b+c)(d+e+f) Z = (a+b-c)(d-e+f) U = (4a+2b+c)(4d+2e+f) V = ad
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句