Аналогичная реализация алгоритма дает разные результаты - PullRequest
Новая
       66

Аналогичная реализация алгоритма дает разные результаты

1 голос
/ 18 июня 2020

Я пытаюсь понять алгоритм умножения Карацубы. Я написал следующий код: 

def karatsuba_multiply(x, y):
    # split x and y
    len_x = len(str(x))
    len_y = len(str(y))
    if len_x == 1 or len_y == 1:
        return x*y

    n = max(len_x, len_y)
    n_half = 10**(n // 2)
    a = x // n_half
    b = x % n_half
    c = y // n_half
    d = y % n_half

    ac = karatsuba_multiply(a, c)
    bd = karatsuba_multiply(b, d)
    ad_plus_bc = karatsuba_multiply((a+b), (c+d)) - ac - bd

    return (10**n * ac) + (n_half * ad_plus_bc) + bd

Этот тестовый пример не работает: 

print(karatsuba_multiply(1234, 5678)) ## returns 11686652, should be 7006652‬

Но если я использую следующий код из этого ответа , тестовый пример дает правильный ответ: 

def karat(x,y):
    if len(str(x)) == 1 or len(str(y)) == 1:
        return x*y
    else:
        m = max(len(str(x)),len(str(y)))
        m2 = m // 2

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

        z0 = karat(b,d)
        z1 = karat((a+b),(c+d))
        z2 = karat(a,c)

        return (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**(m2)) + (z0)

Обе функции выглядят так, как будто они делают одно и то же. Почему моя не работает?

1 Ответ

1 голос
/ 18 июня 2020

Кажется, что в реализации kerat_multiply вы не можете использовать правильную формулу для последнего возврата.

В исходной реализации kerat значение m2 = m // 2 умножается на 2 в последнем возврате (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**(m2)) + (z0) (2 * m2)

Итак, я думаю вам нужно либо добавить новую переменную, как показано ниже, где n2 == n // 2, чтобы вы могли умножить ее на 2 в последнем возвращении, либо использовать исходную реализацию.

Надеюсь, что это поможет :)

РЕДАКТИРОВАТЬ : это объясняется тем, что 2 * n // 2 отличается от 2 * (n // 2)

n = max(len_x, len_y)
n_half = 10**(n // 2)
n2 = n // 2
a = x // n_half
b = x % n_half
c = y // n_half
d = y % n_half

ac = karatsuba_multiply(a, c)
bd = karatsuba_multiply(b, d)
ad_plus_bc = karatsuba_multiply((a + b), (c + d)) - ac - bd

return (10**(2 * n2) * ac) + (n_half * (ad_plus_bc)) + bd
...