Реализация умножения Карацубы

Question

Реализация умножения Карацубы

Недавно я применил умножение Карацубы как личное упражнение. Я написал свою реализацию на Python, следуя псевдокоду, представленному в Википедии:

процедура каратсуба (номер1, номер2)
если (num1 < 10) или (num2 < 10)
    вернуть num1*num2
  /* вычисляет размер чисел */
  m = max(size_base10(num1), size_base10(num2))
  м2 = м /2
  /* разбить последовательность цифр на середину */
  high1, low1 = split_at(num1, m2)
  high2, low2 = split_at(num2, m2)
  /* 3 звонка на номера примерно вдвое меньше */
  z0 = каратсуба (низкий1, низкий2)
  z1 = каратсуба ((низкий1+ высокий1), (низкий2+ высокий2))
  z2 = каратсуба (высокая1, высокая2)
  возврат (z2*10^(2* м2)) + ((z1-z2-z0)*10^(м2)) + (z0)

Вот моя реализация Python:

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)

Мой вопрос об окончательном слиянии z0, z1, а также z2,
z2 сдвинут на m цифр (где m - длина наибольшего из двух умноженных чисел).
Вместо простого умножения на 10 ^ (м), алгоритм использует * 10 ^ (2 * м2) *, где m2 - это м / 2.

Я попытался заменить 2 * m2 на m и получил неправильные результаты. Я думаю, что это связано с тем, как делятся числа, но я не совсем уверен, что происходит.

5

python algorithm recursion karatsuba

Источник

user5478942 19 фев '17 в 06:40

8 ответов

Другие вопросы по тегам python algorithm recursion karatsuba

user7207392 19 фев '17 в 06:57 2017-02-19 06:57 · Answer 1 · 2017-02-19 06:57

В зависимости от вашей версии Python вы должны или должны заменить / с явным оператором разделения этажа // что здесь уместно; это округляет, гарантируя, что ваши показатели остаются целыми числами.

Это важно, например, при разделении ваших операндов на старшие цифры (путем деления по полу на 10^m2) и младшие цифры (принимая остаточное по модулю 10^m2) это не будет работать с дробным m2,

Это также объясняет, почему 2 * (x // 2) не обязательно равен x скорее x-1 если х нечетно. В последней строке алгоритма 2 m2 правильно, потому что то, что вы делаете, дает a а также c их нули обратно.

Если вы используете более старую версию Python, ваш код все еще может работать, потому что / раньше интерпретировалось как деление по полу применительно к целым числам.

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)

user8820616 02 янв '18 в 14:52 2018-01-02 14:52 · Answer 2 · 2018-01-02 14:52

Я реализовал ту же идею, но я ограничил 2-значное умножение в качестве базового случая, потому что я могу уменьшить умножение с плавающей точкой в функции

import math

def multiply(x,y):
    sx= str(x)
    sy= str(y)
    nx= len(sx)
    ny= len(sy)
    if ny<=2 or nx<=2:
        r = int(x)*int(y)
        return r
    n = nx
    if nx>ny:
        sy = sy.rjust(nx,"0")
        n=nx
    elif ny>nx:
        sx = sx.rjust(ny,"0")
        n=ny
    m = n%2
    offset = 0
    if m != 0:
        n+=1
        offset = 1
    floor = int(math.floor(n/2)) - offset
    a = sx[0:floor]
    b = sx[floor:n]
    c = sy[0:floor]
    d = sy[floor:n]
    print(a,b,c,d)

    ac = multiply(a,c)
    bd = multiply(b,d)

    ad_bc = multiply((int(a)+int(b)),(int(c)+int(d)))-ac-bd
    r = ((10**n)*ac)+((10**(n/2))*ad_bc)+bd

    return r

print(multiply(4,5))
print(multiply(4,58779))
print(int(multiply(4872139874092183,5977098709879)))
print(int(4872139874092183*5977098709879))
print(int(multiply(4872349085723098457,597340985723098475)))
print(int(4872349085723098457*597340985723098475))
print(int(multiply(4908347590823749,97098709870985)))
print(int(4908347590823749*97098709870985))

user6448384 16 янв '18 в 20:05 2018-01-16 20:05 · Answer 3 · 2018-01-16 20:05

Я попытался заменить 2*m2 на m и получил неправильные результаты. Я думаю, что это связано с тем, как делятся числа, но я не совсем уверен, что происходит.

Это связано с тем, как вы разделяете свои номера для рекурсивных вызовов. Если вы решили использовать нечетное n затем n//2 будет округлено до ближайшего целого числа, что означает, что ваш второй номер будет иметь длину floor(n/2) и вам придется дополнить первый с floor(n/2) нули. Так как мы используем то же самое n для обоих чисел это относится к обоим. Это означает, что если вы придерживаетесь оригинальной нечетной n для последнего шага, вы будете дополнять первый член оригиналом n нули вместо числа нулей, которые могут возникнуть в результате комбинации первого дополнения и второго дополнения (floor(n/2)*2)

user7940526 30 июл '20 в 15:36 2020-07-30 15:36 · Answer 4 · 2020-07-30 15:36

Вы использовали m2 как поплавок. Это должно быть целое число.

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)

user1718155 05 мар '23 в 02:39 2023-03-05 02:39 · Answer 5 · 2023-03-05 02:39

Мне нужна была версия, которая могла бы хорошо уместиться на одном слайде, не жертвуя ясностью. Вот что я придумал:

      def number_of_digits(number: int) -> int:
    return int(math.log10(abs(number))) + 1

def multiply(x: int, y: int) -> int:
    # We CAN multiply small numbers
    if abs(x) < 10 or abs(y) < 10:
        return x * y

    # Calculate the size of the numbers
    digits = max(number_of_digits(x), number_of_digits(y))
    midpoint = 10 ** (digits // 2)

    # Split digit sequences in the middle
    high_x = x // midpoint
    low_x = x % midpoint
    high_y = y // midpoint
    low_y = y % midpoint

    # 3 recursive calls to numbers approximately half the size
    z0 = multiply(low_x, low_y)
    z1 = multiply(low_x + high_x, low_y + high_y)
    z2 = multiply(high_x, high_y)

    return (z2 * midpoint**2) + ((z1 - z2 - z0) * midpoint) + (z0

print(multiply(2**100, 3**100))

Я бы сказал, что:

имена переменных понятнее
вnumber_of_digitsвспомогательная функция должна использовать log10 для поиска количества цифр вместо str+len
Математика становится немного яснее, если извлечь термин из 10**цифр//2.

user7701381 01 фев '20 в 03:41 2020-02-01 03:41 · Answer 6 · 2020-02-01 03:41

Я думаю, что лучше, если вы использовали math.log10 функция для вычисления количества цифр вместо преобразования в строку, примерно так:

def number_of_digits(number):
  """
  Used log10 to find no. of digits
  """
  if number > 0:
    return int(math.log10(number)) + 1
  elif number == 0:
    return 1
  else:
    return int(math.log10(-number)) + 1 # Don't count the '-'

0

Источник

user7701381 01 фев '20 в 03:41

user10149571 28 июл '18 в 21:23 2018-07-28 21:23 · Answer 7 · 2018-07-28 21:23

Ваш код и логика верны, в базовом случае есть проблема. Так как в соответствии с алгоритмом a,b,c,d являются двузначными числами, вы должны изменить базовый вариант и сохранить длину x и y равной 2 в базовом случае.

0

Источник

user10149571 28 июл '18 в 21:23

user9482853 19 авг '18 в 12:46 2018-08-19 12:46 · Answer 8 · 2018-08-19 12:46

Базовый случай if len(str(x)) == 1 or len(str(y)) == 1: return x*y это неверно. Если вы запустите любой из приведенного в ответах кода Python против больших целых чисел, karat() Функция не даст правильный ответ.

Чтобы сделать код правильным, вам нужно изменить базовый вариант на if len(str(x) < 3 or len(str(y)) < 3: return x*y,

Ниже приведена модифицированная реализация ответа Пола Панцера, который правильно умножает большие целые числа.

def karat(x,y):
    if len(str(x)) < 3 or len(str(y)) < 3:
        return x*y

    n = max(len(str(x)),len(str(y))) // 2

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

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

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