Я работаю над улучшением моих текущих знаний об алгоритмах и сложности. Я пытаюсь реализовать умножение Карацубы в Python.
Я написал свою реализацию, и она работает. Однако всякий раз, когда я запускаю скрипт с двумя аргументами, каждый из которых имеет более 2 цифр, мой вывод оказывается ниже, чем должен быть. Я подозреваю, что есть логическая ошибка, но я не нашел ее.
Я добавил разделение по полу, чтобы числа с 3 цифрами не возвращали число с плавающей точкой. Числа с тремя цифрами теперь возвращают целые числа, с помощью которых я разбиваю строки на сегменты числа.
Тем не менее, я все равно получаю результат ниже ожидаемого. Это из-за разделения этажа?
Большое спасибо за любую помощь или комментарии.
def karatsuba(x, y):
n = len(str(x))
if 1 == len(str(x)) or 1 == len(str(y)):
return x * y
else:
# Get strings of x and y
x_str, y_str = str(x), str(y)
# Get half lengths of x and y
x_len, y_len = int(len(x_str) // 2), int(len(y_str) // 2)
a = int(x_str[: x_len])
b = int(x_str[x_len:])
c = int(y_str[:y_len])
d = int(y_str[y_len:])
p = a + b
q = c + d
ac = karatsuba(a, c)
bd = karatsuba(b, d)
pq = karatsuba(p, q)
adbc = pq - ac - bd
return 10**n * ac + 10**(n/2) * adbc + bd
test1, test2 = 1234, 5678
print(karatsuba(test1, test2))
print(test1 * test2)
print(karatsuba(test1, test2) == test1 * test2) # Should show True
test1, test2 = 1234, 5678
Ожидаемые результаты:
7006652
7006652
True
Фактические результаты:
6592652.0
7006652
False