Я хочу реализовать умножение Карацубы в Python

Question

Я хочу реализовать умножение Карацубы в Python.

Но я получаю правильный ответ, когда число большое.

Может кто-нибудь сказать мне, где мой код не так？

Реализация умножения Карацубы неверна, когда х очень большой.

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")