Умножение на Karatsuba за неравен размер, не-степен на 2 операнди

Кой е най-ефективният начин за прилагане на Karatsuba умножение на големи числа с входни операнди с различен размер и чийто размер е не е степен на 2 и може би дори не е четно число? Подпълването на операндите означава допълнителна памет и искам да опитам да го направя паметефективно.

Едно от нещата, които забелязвам в нечетния размер на Карацуба е, че ако се опитаме да разделим числото на „половини“ възможно най-близо до четното, едната половина ще има m+1 елемента, а другата m, където m = floor(n/2), като n е броят на елементите в разделното число. Ако и двете числа са с еднакъв нечетен размер, тогава трябва да изчислим продукти от две числа с размер m+1, изискващи n+1 памет, за разлика от n в случая, когато n е четно. Така че прав ли съм в предположението, че Karatsuba за нечетни размери може да изисква малко повече памет, отколкото за четни размери?


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

През повечето време дължината на операндите няма да бъде степен на 2. Мисля, че това е рядък случай. През повечето време ще има различни дължини на операндите. Но това няма да е проблем за Карацуба алго.

Всъщност не виждам никакъв проблем тук. Тази режийна (странна дължина) е толкова лека и определено не е голяма работа. Задача за различни дължини - нека приемем, че 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;

И, ако приемем, че можем лесно да умножим 2-цифрени числа - можете да получите отговора = 55530. Същото, както просто да умножите 1234 * 45 във всеки калкулатор :) И така, не виждам никакъв проблем с паметта при различни дължини на числа.

person Mysterion    schedule 12.08.2013
comment
ако x = 123 тогава как можете да разделите числото на две части? - person Mastan; 16.10.2015
comment
a = 1, b = 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

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

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

arrow_upward
1
arrow_downward

Можете да умножите числата по степени на 10, така че всяко от тях да има четен брой цифри. Приложете алгоритъма на karatsuba и разделете отговора на коефициента на степен 10, който сте умножили първоначалните 2 числа, за да ги направите четни.

Eg: 123*12

Изчислете 1230*1200 и разделете отговора на 1000.

person user1825567    schedule 04.05.2018