python - 我想在 python 中实现 Karatsuba 乘法

Question

我想在 python 中实现 Karatsuba 乘法。

但是当数字很大时我得到了正确的答案。

谁能告诉我我的代码哪里错了？

Karatsuba Multiplication Implementation当 x 很大时是不对的。

import math
def fun1(x,y):
    if x <= 100  or y<=100:
        return x*y
    else:
        n = int(math.log10(x)) + 1
        print(n)
        #split x
        a = int(x//(10**int(n/2)))
        b = int(x%(10**int(n/2)))
        #split y
        c = int(y//(10**int(n/2)))
        d = int(y%(10**int(n/2)) )
        print('=======')
        print(a,b,c,d)
        s1 = fun1(a,c)
        s2 = fun1(b,d)
        s3 = fun1(a+b, c+d) - s1 -s2

        return 10**(n) * s1 + 10**int(n/2) * s3 + s2
x = 3141592653589793238462643383279502884197169399375105820974944592
y = 3141592653589793238462643383279502884197169399375105820974944592
res = fun1(x,y)
print(res)

这里是结果对比:

mine: 9871629289354805781531825310608443798018906328629821071675205208766177059699451037253550917606373321601467241501439093564279364
x**2: 9869604401089358618834490999876151135313699407240790626413349374285977301132874762146178862115173871455167598223967837470046464

Answer 1

问题出在函数的最后一行:

return 10**(n) * s1 + 10**int(n/2) * s3 + s2

当 n 是偶数时，这可以正常工作，但是当 n 是奇数时，您需要将 s1 乘以 10 的幂比要求的大——s1 的移动量应该正好是 s3 的两倍。

我稍微重构了你的代码。这应该有效:

import math, random

def karatsuba(x,y):
    if x <= 100  or y<=100:
        return x * y
    else:
        n = 10 ** int(math.log10(x) / 2.0 + 0.5)
        a, b = x // n, x % n
        c, d = y // n, y % n
        s1 = karatsuba(a,c)
        s2 = karatsuba(b,d)
        s3 = karatsuba(a+b, c+d) - s1 - s2
        return n * n * s1 + n * s3 + s2

for i in range(100):
    x = random.randint(1, 2**1024)
    y = random.randint(1, 2**1024)
    assert karatsuba(x,y) == x * y
else:
    print("OK")