почему этот код возвращает отрицательный ответ при умножении Карацубы

    """karatsuba algo"""
def fast(x,y):
    if len(str(x))==1 or len(str(y))==1:
        return x*y
    else:
        n = max(len(str(x)),len(str(y)))
        m = n//2

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

        k = fast(a,c)
        n = fast((a+b),(c+d))
        o = fast(b,d)

        return (10**2*m*k) +(10**m*(n-k-o))+(o)
print(fast(10515610,5651551460))

у python не должно быть проблем с переполнением. Тогда почему он возвращает отрицательный ответ, когда ввод большой?


python karatsuba
person rohit datta    schedule 11.06.2020    source источник
comment
Это не так. Если вы попробуете print(fast(1051599610,5651460)), вы получите 441780299400 Так что это вызвано операциями.   -  person Ann Zen    schedule 11.06.2020
comment
Единственным источником отрицательных чисел для положительных входных данных является n-k-o. Поэтому, если вы видите отрицательный результат, можно предположить, что в какой-то момент n < k+o.   -  person Tom Karzes    schedule 11.06.2020
comment
10**2*m*k неправильно заключен в скобки.   -  person user2357112 supports Monica    schedule 11.06.2020

Ответы (2)


arrow_upward
0
arrow_downward

Глядя на исходный алгоритм, ваш код должен быть

return (10**(2*m)*k) +(10**m*(n-k-o))+(o)

Посмотрите на дополнительные скобки вокруг (2*m). В противном случае вы умножаете на m вместо возведения в степень.

Вероятно, вы могли бы сделать все это более читабельным и эффективным, заменив все биты 10**m новой переменной

person JBernardo    schedule 11.06.2020

arrow_upward
-1
arrow_downward

Я проверил это и обнаружил, что проблема не в переполнении Python. Ваше значение o в последней итерации слишком велико по сравнению с k или n. И k, и n получили значение 6, а o содержит 17487400. Таким образом, n-k-o вызвало отрицательный результат.

person EduardoSaverin    schedule 11.06.2020