Умножение Карацубы - Как решить выход ниже ожидаемого? - PullRequest
Новая
       15

Умножение Карацубы - Как решить выход ниже ожидаемого?

0 голосов
/ 24 января 2019

Я работаю над улучшением моих текущих знаний об алгоритмах и сложности. Я пытаюсь реализовать умножение Карацубы в 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
...