python - Karatsuba 算法 - 我的实现错误

Question

我在 python 中实现 karatsuba 算法时遇到了问题。我正在使用 base 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 实现:

def karatsuba(A, B):
    if(len(A) == 1 or len(B) == 1):
        return Multiply(A, B)

    n = max(len(A), len(B))
    m = n / 2

    print "Karatsuba call"

    print "A", A, "\n"
    print "B", B, "\n"

    lowA = A[:m]
    highA = A[m:]

    lowB = B[:m]
    highB = B[m:]

    print "highA", highA, "\n"
    print "lowA", lowA, "\n"

    print "highB", highB, "\n"
    print "lowB", lowB, "\n"

    s1 = karatsuba(highA, highB)
    s2 = karatsuba(lowA, lowB)
    s3 = karatsuba(Add(highA, lowA), Add(highB, lowB))

    f1 = Multiply(s1, pow2(n))
    f2 = Multiply(Sub(Sub(s3, s1), s2), pow2(m))
    return Add(f1, Add(f2, s2))

但是随着输入运行(记住 MSB 是最右边的位):

A [0, 1, 1] 
B [0, 1, 1] 

我得到 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))

应该是:

f1 = Multiply(s1, pow2(2*m))

的确，(a1*2^m+a0)*(b1*2^m+b0)=(a1*b1)*2^(2m) + (a0*b1+a1*b0)* 2^m + (a0*b0)

如果 n > (2*m)，即 n 为奇数，那么你做错了......