时间戳

首页 > 解决方案 > 我想在 python 中实现 Karatsuba 乘法

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

问题描述

我想在 python 中实现 Karatsuba 乘法。

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

谁能告诉我我的代码哪里错了？</p>

当 x 很大时，Karatsuba 乘法实现是不正确的。

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

标签： pythonalgorithmkaratsuba

解决方案

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

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

当n是偶数时，这可以正常工作，但当n是奇数时，你乘以s110 的幂，比所需的大一倍——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")

推荐阅读