Блог

Главная - Вопросы по программированию - Кодирование умножения Карацубы

Кодирование умножения Карацубы

#python #karatsuba

#python #карацуба

Вопрос:

мой приведенный ниже код, похоже, работает хорошо, если длина любого из чисел четная, но если обе длины числа нечетные (как на рисунке), он выдает неверный результат. Я понятия не имею, где что-то пошло не так или как это исправить.

 def karatsubaMulti(num1, num2):
    len1 = len(str(num1))
    len2 = len(str(num2))

    if len1==1 or len2==1:
        return num1*num2

    else:
        maxLen = max(len1, len2)

        if maxLen > len1:
            a=0
            b=num1
        else:
            a = num1 // pow(10, maxLen//2)
            b = num1 %  pow(10, maxLen//2)

        if maxLen > len2:
            c=0
            d=num2
        else:
            c = num2 // pow(10, maxLen//2)
            d = num2 % pow(10, maxLen//2)
        z1 = karatsubaMulti(a, c)
        z2 = karatsubaMulti(b, d)
        z3 = karatsubaMulti(a b, c d)
        return z1 * pow(10, maxLen)   (z3-z1-z2) * pow(10, maxLen//2)   z2
x = 171
y = 571

xy1 = karatsubaMulti(x, y)

print(xy1)

Комментарии:

1. Пожалуйста, вставьте код в виде текста в свой вопрос, а не в виде изображения. Добро пожаловать в SO.

2. Вы можете форматировать код в stackoverflow между могилами с тройным ударением.

3. теперь он отредактирован, спасибо

4. Замечание: реализовать это так в Python совершенно бесполезно, потому что одно деление на большое число (10 ^ что-то большое) уже дороже, чем умножение. // Кстати, вы можете использовать ** для оператора мощности.

5. Это просто практика рекурсивных вызовов. В любом случае спасибо

Ответ №1:

Внимательно посмотрите на формулу, сравните ее с правильной формулой, и вы увидите, что квадрат pow(10, maxLen//2) не pow(10, maxLen) равен .

Комментарии:

1. Я вижу, что здесь предлагается. Но когда дело доходит до нечетной длины, что мне делать, чтобы исправить эту проблему?

2. @n.y Теперь вы знаете, где ошибка, попробуйте разобраться сами.