Умножение Карацубы для неравных по размеру операндов, отличных от степени двойки

Каков наиболее эффективный способ реализации Karatsuba умножения больших чисел с входными операндами неравного размера, размер которых не степень 2 и, возможно, даже не четное число? Заполнение операндов означает дополнительную память, и я хочу попытаться сделать ее эффективной с точки зрения использования памяти.

Одна из вещей, которую я заметил в нечетном размере Карацубы, заключается в том, что если мы попытаемся разделить число на «половины» как можно ближе к четному, одна половина будет иметь m + 1 элемент, а другая m, где m = floor(n/2), n — количество элементов в разбиваемом числе. Если оба числа имеют один и тот же нечетный размер, то нам нужно вычислить произведения двух чисел размера m+1, что требует хранения n+1, в отличие от n в случае, когда n четно. Итак, я прав, предполагая, что Карацуба для нечетных размеров может потребовать немного больше памяти, чем для четных размеров?


algorithm multiplication largenumber
person The_Sympathizer    schedule 12.05.2013    source источник
comment
Этот предыдущий вопрос SO содержит некоторые детали реализации, которые могут помочь   -  person Zim-Zam O'Pootertoot    schedule 12.05.2013

Ответы (3)


arrow_upward
7
arrow_downward

В большинстве случаев длина операндов не будет степенью двойки. Я думаю, что это редкий случай. Большую часть времени операнды будут разной длины. Но это не будет проблемой для алгоритма Карацубы.

Собственно, я не вижу здесь никакой проблемы. Эти накладные расходы (нечетной длины) очень легкие и определенно не имеют большого значения. Проблема с разной длиной - допустим, что X = 1234 и Y = 45

Итак, a = 12, b = 34, c = 0, d = 45 Итак, после этого X * Y = 10 ^ 4 * ac + 10 ^ 2 (ad + bc) + bd

ac = 0;
bd = 34 * 45;
ad + bc = (a + b) * (c + d) - ac - bd = 540;

И, если предположить, что мы могли бы легко умножать двузначные числа - вы могли бы получить ответ = 55530. Так же, как просто умножить 1234 * 45 в любом калькуляторе :) Так что я не вижу никакой проблемы с памятью с разной длиной числа.

person Mysterion    schedule 12.08.2013
comment
если x = 123, то как можно разделить число на две части? - person Mastan; 16.10.2015
comment
а = 1, б = 23, я думаю. - person Mysterion; 17.10.2015
comment
Нет, я думаю, что этот алгоритм не будет работать, если n-битное число является нечетным числом цифр. - person Mastan; 18.10.2015
comment
@Mastan, можешь проверить мое решение? - person user1825567; 04.05.2018

arrow_upward
1
arrow_downward

Чтобы ответить на ваши сомнения в комментариях выше. Хитрость заключается в том, чтобы следовать формуле для расчета степени 10 в случае десятичного расчета.

10^2m(A.C) + 10^m((A+B).(C+D)-A.C-B.D) + B.D

m = n/2 + n%2

n is length of number

Обратитесь к вики, там подробно объясняется.

person pratikpawar    schedule 26.01.2017
comment
n is length of number - какое из 2-х умноженных чисел? - person Undefitied; 05.07.2019

arrow_upward
1
arrow_downward

Вы можете умножать числа на степени 10 так, чтобы в каждом из них было четное количество цифр. Примените алгоритм Карацубы и разделите ответ на коэффициент степени 10, на который вы умножили исходные 2 числа, чтобы сделать их четными.

Eg: 123*12

Вычислите 1230*1200 и разделите результат на 1000.

person user1825567    schedule 04.05.2018