Каратсуба умножение имеет ошибку с большим числом

Я написал одну версию моего кода Python. Базовые тестовые примеры кажутся хорошими, в то время как случай с очень большим числом karatsuba(3141592653589793238462643383279502884197169399375105820974944592, 2718281828459045235360287471352662497757247093699959574966967627) не будет правильным Можете ли вы посоветовать, где не правильно код? Env - это python3.

def karatsuba(x,y):
    if x<10 and y < 10:
        return x*y
    x_len=len(str(x))
    y_len=len(str(y))
    n=max(x_len,y_len)
    m=int(n/2)

    a=int(x/(10**m))
    b=int(x%(10**m))
    c=int(y/(10**m))
    d=int(y%(10**m))

    ac=karatsuba(a,c)
    bd=karatsuba(b,d)
    sum_sum=karatsuba(a+b,c+d)
    adbc=sum_sum-ac-bd
    return int((10**(2*m))*ac+(10**m)*adbc+bd)

result=karatsuba(3141592653589793238462643383279502884197169399375105820974944592,
                 2718281828459045235360287471352662497757247093699959574966967627)
#result=karatsuba(1234,8765)
#result=karatsuba(100,23)
print(result)

0 ответов

Другие вопросы по тегам