我的实现中的Karatsuba算法错误

Question

我在python中实现karatsuba算法时遇到了困难。我使用的是基2中的列表（MSB在列表的末尾）。给我的实现是：

Input: 2 bit-numbers of bit length n
Output: their product a*b

function Karatsuba(a, b) 
     if(n == 1) return a*b
     else 
          a1, a0, leftmost(n/2)(rounded up), rightmost(n/2)(rounded down) bits of a
          b1, b0, leftmost(n/2)(rounded up), rightmost(n/2)(rounded down) bits of b

     s1 = Karatsuba(a1, b1)
     s2 = Karatsuba(a0, b0)
     s3 = Karatsuba(a1 + a0, b1 + b0)

     return s1 * 2^n + (s3 - s1 - s2) * 2^(n/2) + s2

这是我的python实现：

^{pr2}$

但是使用输入运行（记住MSB是最右边的位）：

^{3}$

我得到Product Karatsuba [0, 0, 0, 1, 0, 0, 1, 0] 72，但它应该输出[0, 0, 1, 0, 0, 1] 36。函数Add、Substract、pow2和Multiply都在工作，我分别测试了它们。如果有帮助的话，下面是打印语句的完整输出：

Karatsuba call
A [0, 1, 1] 

B [0, 1, 1] 

highA [1, 1] 

lowA [0] 

highB [1, 1] 

lowB [0] 

Karatsuba call
A [1, 1] 

B [1, 1] 

highA [1] 

lowA [1] 

highB [1] 

lowB [1] 

Karatsuba call
A [0, 1] 

B [0, 1] 

highA [1] 

lowA [0] 

highB [1] 

lowB [0] 

Karatsuba call
A [1, 1] 

B [1, 1] 

highA [1] 

lowA [1] 

highB [1] 

lowB [1] 

Karatsuba call
A [0, 1] 

B [0, 1] 

highA [1] 

lowA [0] 

highB [1] 

lowB [0] 

我找了几个小时，我不知道我的错误在哪里。有人能帮帮我吗？谢谢

Answer 1

错误是这样的：

f1 = Multiply(s1, pow2(n))

它应该是：

^{pr2}$

事实上，(a1*2^m+a0)*(b1*2^m+b0)=(a1*b1)*2^(2m) + (a0*b1+a1*b0)*2^m + (a0*b0)

如果n > (2*m)，那就是奇数n，那么你做得不对。。。在