Karacubin algoritam

Karacubin algoritam je algoritam za brzo množenje. Otkrio ga je Anatolji Karacuba 1960 i objavio 1962. Smanjuje množenje dva n- tocifrena broja na najviše $n^{\log _{2}3}\approx n^{1.585}$ jednocifreno množenje (i tačno $n^{\log _{2}3}$ gde je n stepen 2). Zato je brži od klasičnog algoritma množenja, koji zahteva n² jednocifren proizvoda. Na primer, Karacubin algoritam zahteva 3¹⁰ = 59,049 jednocifrenih množenja za množenje dva 1024-cifrena broja (n = 1024 = 2¹⁰), dok klasičan algoritam zahteva (2¹⁰)² = 1,048,576.

Karacubin algoritam je prvi algoritam množenja koji je asimptotički brži od kvadratnog "školskog" algoritma množenja. "Toom–Cook" algoritam je brža generalizacija Karacubinog algoritma, dok je "Schönhage–Strassen" algoritam još brži, za dovoljno veliko n.

Istorija

Standardna procedura množenja dva n-tocifrena broja zahteva broj elementarnih operacija proporcionalan $n^{2}\,\!$, ili $\Theta (n^{2})\,\!$ u za veliko O. Andrej Kolomogrov je 1952 pretpostavio da je klasičan algoritam bio asimptotski optimalan, tj. da bi svaki algoritam zahtevao $\Omega (n^{2})\,\!$ elementarnih operacija.

Kolomogorov je, 1960 u moskovskom državnom univerzitetu, organizovao matematički seminar na temu problema u kibernetici, kada je izjavio da su sa $\Omega (n^{2})\,\!$ zasnovani i ostali problemi u teoriji kompleksnosti. Nedelju dana kasnije, Karacuba, 23-godišnjni student, napravio je algoritam (kasnije nazvan "podeli pa vladaj") koji množi dva n-tocifrena brojeva u $\Theta (n^{\log _{2}3})$ elementarnih koraka, i time oborio pretpostavku. Kolomogorov je bio vidno potrešen otkrićem; on je saopštio otkriće na sledećem seminaru, koji je bio zatim prekinut. Kolomogorov je predavao neke lekcije na temu Karacubinih rezultata na konferencijama širom sveta (pogledati, na primer, "Proceedings of the international congress of mathematicians 1962". str. 351--356, i takođe "6 Lectures delivered at the International Congress of Mathematicians in Stockholm, 1962") i objavio algoritam 1962, u naučnim novinama ("Proceedings of the USSR Academy of Sciences"). Članak je napisao Kolomogorov i sadržao je dva rezultata množenja, Karacubin algoritam i odvojene rezultate Jurija Petroviča Ofmana; članak je imao naslov "A. Karacuba i Ju. Ofman" kao i autore teksta. Karacuba je saznao za tekst tek kada je dobio kopiju od izdavača.

Algoritam

Osnovni koraci

Osnovni korak Karacubinog algoritma je formula koja omogućava izračunavanje proizvoda dva velika broja $x$ and $y$ koristeći tri množenja malih brojeva, svaki sa oko pola cifara kao $x$ ili $y$, i još neka sabiranja i pomeranje (šiftovanje) cifara.

Neka $x$ i $y$ budu prikazani kao $n$-tocifrenih stringova u nekoj bazi $B$. Za bilo koji pozitivan ceo broj $m$ manji od $n$, mogu se zapisati dva data broja kao:

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

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

gde $x_{0}$ i $y_{0}$ su manjni od $B^{m}$. Proizvod je onda

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

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

gde

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

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

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

Ove formule zahtevaju množenje, i poznate se po Čarls Bebidžu. Karacuba je pretpostavio da $xy$ mogu biti izračunati u samo tri množenja, sa cenom nekoliko dodatnih sabiranja. Sa $z_{0}$ i $z_{2}$ kao i pre može se izračunati

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

koji ima

$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}$.

Efikasnija implementacija Karacubinog algoritma množenja se može predstaviti kao $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}$.

Primer

Da bismo izračunali proizvod 12345 i 6789, izabraćemo da je B = 10 i m = 3. Onda razlažemo ulazne operande koristeći dobijenu bazu (B^m = 1000), kao:

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

Samo tri množenja, koja se odvijaju na malim celim brojevima, se koriste za izračunavanje tri delimična tj. partitivna rezultata:

z₂ = 12 × 6 = 72

z₀ = 345 × 789 = 272205

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

Reѕultat dobijamo samo sabirajući ova tri delimična rezultata, pomeramo ih prema (i zatim razlažemo ova tri ulaza u bazu 1000 kao za ulazne operande):

rešenje= z₂ · B^2m + z₁ · B^m + z₀, i.e.

rešenje = 72 · 1000² + 11538 · 1000 + 272205 = 83810205.

Primetite da srednje treće množenje operiše na ulaznom domenu koji je dvaput manji od prva dva množenja , njegov izlazni domen je četiri puta manji, i baza -1000 koja sadrži prva dva množenja koja se moraju uzeti u obzir prilikom oduzimanja; takođe primetite da ovo partitivno rešenje z₁ ne može biti negativno: da bismo izračunali ova oduzimanja, koristićemo sabiranje sa komplementom 1000² koji se takođe može koristiti, čuvajući samo poslednje 2 baze -1000 cifara za svaki broj:

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

Rekurzivna aplikacija

Ako je n četiri ili više, množenje u tri koraka u osnovi Karacubinog algoritma je da uključi operande sa više od n cifara. Zato, ovi proizvodi mogu biti izračunati rekurzivnim pozivom. Rekurzija će se ponavljati sve dok brojevi ne budu toliko mali da tada moraju da budu direktno pomnoženi.

Na računaru sa 32-bita, na primer, može se izabrati B = 2³¹ = 2,147,483,648 or B = 10⁹ = 1,000,000,000, i smestiti svaka cifra kao odvojena 32-bitna binarna reč. Onda suma x₁ + x₀ i y₁ + y₀ neće zahtevati dodatnu binarnu reč za smeštanje prenete cifre, i Karacubina rekurzija može biti primenjena sve dok brojevi koji se množe su dužine jedne cifre..

Analiza efikasnosti

Karacubin osnovni korak radi za bilo koju bazu B i bilo koje m, ali rekurzivni algoritam je najefikasniji kada je m jednako n/2, zaokruženo. Naročito, ako n je 2^k, za neki ceo broj k, i rekurzija staje samo kada n postane 1, onda broj jednocifrenic množenja je 3^k, što je n^c gde je c = log₂3.

Pošto se može povećati bilo koji ulaz sa nula cifara sve dok dužina ne postane stepen dvojke , iz toga sledi da broj elementarnih množenja , za bilo koje n, je najviše $3^{\lceil \log _{2}n\rceil }\leq 3n^{\log _{2}3}\,\!$.

Pošto se sabiranje, oduzimanje, i pomeranje cifara (množenje bazom B) u Karacubinom osnovnom koraku uzima vreme proporcionalno n, ta cena postajae zanemarljiva za n koje raste. Preciznije, ako t(n) označava ukupan brroj elementarnih operacija koij algoritam izvodi prilikom množenja dva n-tocifrena broja, onda

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

za neke konstante c and d. Za ovu diferencnu relaciju, master teorema daje asimptotsku granicu $T(n)=\Theta (n^{\log _{2}3})\,\!$.

Iz toga sledi, za dovoljno veliko n, Karacubinalgoritam će izvesti nekoliko pomeranja i jednocifrenih sabiranja onda dukačko množenje, iako osnovni korak koristi više sabiranja i pomeranja nego formula. Za male vrednosti n, kako god, dodatno pomeranje i sabiranje mogu usporiti u odnosu na duhačku metodu množenja. Poenta pozitivnog povratka zavisi od platforme i konteksta. Kao neko pravilo, Karacubin algoritam je brži kada su množenik i množilac duži od 320–640 bitova.

Pseudokod

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)

Spoljašnje veze

• 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++