Карацубин алгоритам

Карацубин алгоритам је алгоритам за брзо множење. Открио га је Анатољи Карацуба 1960 и објавио 1962. Смањује множење два n- тоцифрена броја на највише $n^{\log _{2}3}\approx n^{1.585}$ једноцифрено множење (и тачно $n^{\log _{2}3}$ где је n степен 2). Зато је бржи од класичног алгоритма множења, који захтева n² једноцифрен производа. На пример, Карацубин алгоритам захтева 3¹⁰ = 59,049 једноцифрених множења за множење два 1024-цифрена броја (n = 1024 = 2¹⁰), док класичан алгоритам захтева (2¹⁰)² = 1,048,576.

Карацубин алгоритам је први алгоритам множења који је асимптотички бржи од квадратног "школског" алгоритма множења. "Toom–Cook" алгоритам је бржа генерализација Карацубиног алгоритма, док је "Schönhage–Strassen" алгоритам још бржи, за довољно велико n.

Историја

Стандардна процедура множења два n-тоцифрена броја захтева број елементарних операција пропорционалан $n^{2}\,\!$, или $\Theta (n^{2})\,\!$ у за велико О. Андреј Коломогров је 1952 претпоставио да је класичан алгоритам био асимптотски оптималан, тј. да би сваки алгоритам захтевао $\Omega (n^{2})\,\!$ елементарних операција.

Коломогоров је, 1960 у московском државном универзитету, организовао математички семинар на тему проблема у кибернетици, када је изјавио да су са $\Omega (n^{2})\,\!$ засновани и остали проблеми у теорији комплексности. Недељу дана касније, Карацуба, 23-годишњни студент, направио је алгоритам (касније назван "подели па владај") који множи два n-тоцифрена бројева у $\Theta (n^{\log _{2}3})$ елементарних корака, и тиме оборио претпоставку. Коломогоров је био видно потрешен открићем; он је саопштио откриће на следећем семинару, који је био затим прекинут. Коломогоров је предавао неке лекције на тему Карацубиних резултата на конференцијама широм света (погледати, на пример, "Proceedings of the international congress of mathematicians 1962". стр. 351--356, и такође "6 Lectures delivered at the International Congress of Mathematicians in Stockholm, 1962") и објавио алгоритам 1962, у научним новинама ("Proceedings of the USSR Academy of Sciences"). Чланак је написао Коломогоров и садржао је два резултата множења, Карацубин алгоритам и одвојене резултате Јурија Петровича Офмана; чланак је имао наслов "A. Карацуба и Ју. Офман" као и ауторе текста. Карацуба је сазнао за текст тек када је добио копију од издавача.

Алгоритам

Основни кораци

Основни корак Карацубиног алгоритма је формула која омогућава израчунавање производа два велика броја $x$ and $y$ користећи три множења малих бројева, сваки са око пола цифара као $x$ или $y$, и још нека сабирања и померање (шифтовање) цифара.

Нека $x$ и $y$ буду приказани као $n$-тоцифрених стрингова у некој бази $B$. За било који позитиван цео број $m$ мањи од $n$, могу се записати два дата броја као:

$x=x_{1}B^{m}+x_{0}$

$y=y_{1}B^{m}+y_{0}$,

где $x_{0}$ и $y_{0}$ су мањни од $B^{m}$. Производ је онда

$xy=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})$

$xy=z_{2}B^{2m}+z_{1}B^{m}+z_{0}$,

где

$z_{2}=x_{1}y_{1}$

$z_{1}=x_{1}y_{0}+x_{0}y_{1}$

$z_{0}=x_{0}y_{0}$.

Ове формуле захтевају множење, и познате се по Чарлс Бебиџу. Карацуба је претпоставио да $xy$ могу бити израчунати у само три множења, са ценом неколико додатних сабирања. Са $z_{0}$ и $z_{2}$ као и пре може се израчунати

$z_{1}=(x_{1}+x_{0})(y_{1}+y_{0})-z_{2}-z_{0}$

који има

$z_{1}=x_{1}y_{0}+x_{0}y_{1}$

$z_{1}=(x_{1}+x_{0})(y_{1}+y_{0})-x_{1}y_{1}-x_{0}y_{0}$.

Ефикаснија имплементација Карацубиног алгоритма множења се може представити као $xy=(b^{2}+b)x_{1}y_{1}-b(x_{1}-x_{0})(y_{1}-y_{0})+(b+1)x_{0}y_{0}$, where $b=B^{m}$.

Пример

Да бисмо израчунали производ 12345 и 6789, изабраћемо да је B = 10 и m = 3. Онда разлажемо улазне операнде користећи добијену базу (B^m = 1000), као:

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

Само три множења, која се одвијају на малим целим бројевима, се користе за израчунавање три делимична тј. партитивна резултата:

z₂ = 12 × 6 = 72

z₀ = 345 × 789 = 272205

z₁ = (12 + 345) × (6 + 789) − z₂ − z₀ = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

Реѕултат добијамо само сабирајући ова три делимична резултата, померамо их према (и затим разлажемо ова три улаза у базу 1000 као за улазне операнде):

решење= z₂ · B^2m + z₁ · B^m + z₀, i.e.

решење = 72 · 1000² + 11538 · 1000 + 272205 = 83810205.

Приметите да средње треће множење оперише на улазном домену који је двапут мањи од прва два множења , његов излазни домен је четири пута мањи, и база -1000 која садржи прва два множења која се морају узети у обзир приликом одузимања; такође приметите да ово партитивно решење z₁ не може бити негативно: да бисмо израчунали ова одузимања, користићемо сабирање са комплементом 1000² који се такође може користити, чувајући само последње 2 базе -1000 цифара за сваки број:

z₁ = 283815 − 72 − 272205 = (283815 + 999928 + 727795) mod 1000² = 2011538 mod 1000² = 11538.

Рекурзивна апликација

Ако је n четири или више, множење у три корака у основи Карацубиног алгоритма је да укључи операнде са више од n цифара. Зато, ови производи могу бити израчунати рекурзивним позивом. Рекурзија ће се понављати све док бројеви не буду толико мали да тада морају да буду директно помножени.

На рачунару са 32-бита, на пример, може се изабрати B = 2³¹ = 2,147,483,648 or B = 10⁹ = 1,000,000,000, и сместити свака цифра као одвојена 32-битна бинарна реч. Онда сума x₁ + x₀ и y₁ + y₀ неће захтевати додатну бинарну реч за смештање пренете цифре, и Карацубина рекурзија може бити примењена све док бројеви који се множе су дужине једне цифре..

Анализа ефикасности

Карацубин основни корак ради за било коју базу B и било које m, али рекурзивни алгоритам је најефикаснији када је m једнако n/2, заокружено. Нарочито, ако n је 2^k, за неки цео број k, и рекурзија стаје само када n постане 1, онда број једноцифрениц множења је 3^k, што је n^c где је c = log₂3.

Пошто се може повећати било који улаз са нула цифара све док дужина не постане степен двојке , из тога следи да број елементарних множења , за било које n, је највише $3^{\lceil \log _{2}n\rceil }\leq 3n^{\log _{2}3}\,\!$.

Пошто се сабирање, одузимање, и померање цифара (множење базом B) у Карацубином основном кораку узима време пропорционално n, та цена постајае занемарљива за n које расте. Прецизније, ако t(n) означава укупан бррој елементарних операција коиј алгоритам изводи приликом множења два n-тоцифрена броја, онда

$T(n)=3T(\lceil n/2\rceil )+cn+d$

за неке константе c and d. За ову диференцну релацију, мастер теорема даје асимптотску границу $T(n)=\Theta (n^{\log _{2}3})\,\!$.

Из тога следи, за довољно велико n, Карацубиналгоритам ће извести неколико померања и једноцифрених сабирања онда дукачко множење, иако основни корак користи више сабирања и померања него формула. За мале вредности n, како год, додатно померање и сабирање могу успорити у односу на духачку методу множења. Поента позитивног повратка зависи од платформе и контекста. Као неко правило, Карацубин алгоритам је бржи када су множеник и множилац дужи од 320–640 битова.

Псеудокод

procedure karatsuba(num1, num2)
  if (num1 < 10) or (num2 < 10)
    return num1*num2
  /* рачуна величину бројева */
  m = max(size_base10(num1), size_base10(num2))
  m2 = m/2
  /* дели на пола секвенце цифара */
  high1, low1 = split_at(num1, m2)
  high2, low2 = split_at(num2, m2)
  /* 3 позива направи за отприлике половину величине бројева */
  z0 = karatsuba(low1,low2)
  z1 = karatsuba((low1+high1),(low2+high2))
  z2 = karatsuba(high1,high2)
  return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)

Спољашње везе

• Karatsuba's Algorithm for Polynomial Multiplication
• Karatsuba multiplication Algorithm – Web Based Calculator (GPL)
• Bernstein, D. J., "Multidigit multiplication for mathematicians". Covers Karatsuba and many other multiplication algorithms.
• Karatsuba Multiplication on Fast Algorithms and the FEE
• Karatsuba multiplication in C++