Algoritmo de Karacuba

La **algoritmo de Karacuba** estas algoritmo por multipliko de grandaj nombroj. Ĝi ebligas fari la multiplikon de du *n*-ciferaj nombroj per maksimume 3 n^{\log_23}\approx 3 n^{1,585} unu-ciferaj multiplikoj ĝenerale. La kvanto de la unu-ciferaj multiplikoj estas akurate n^{\log_{2}{3}}= 3^{\log_{2}{n}} se *n* estas entjera potenco de 2. Ĝi estas pro tio pli rapida ol la klasika longa multiplika algoritmo, kiu postulas *n2* unu-ciferaj multiplikojn.

Se ekzemple *n = 210 = 1024*, la kvanto de la unu-ciferaj multiplikoj ĉe algoritmo de Karacuba estas 310 = 59049; kaj la kvanto de la unu-ciferaj multiplikoj ĉe klasika longa multipliko estas (210)2 = 1048576.

## Algoritmo 
### La baza paŝo 
La baza paŝo de algoritmo de Karacuba estas formulo kiu permesas komputi la produton de du nombroj *x* kaj *y* per tri multiplikoj de pli malgrandaj nombroj, ĉiu kun proksimume duono da ciferoj kiel *x* aŭ *y*, kaj iu kvanto de adicioj.

Estu *x* kaj *y* prezentitaj kiel *n*-ciferaj en iu bazo *B*. Por ĉiu pozitiva entjero *m* malpli granda ol *n*, unu povas fendi ĉiuj el la du donitaj nombroj kiel

:*x = x1Bm + x0*
:*y = y1Bm + y0*

kie *x0* kaj *y0* estas malpli grandaj ol *Bm*. La produto estas tiam

: *xy = (x1Bm + x0)(y1Bm + y0) = z2 B2m + z1 Bm + z0*

kie

: *z2 = x1y1*
: *z1 = x1y0 + x0y1*
: *z0 = x0y0*

Ĉi tiuj formuloj prezentas la klasikan longan multiplikan algoritmon kaj postulas kvar multiplikoj. La algoritmo de Karacuba estas la komputado de *z0*, *z1* kaj *z2*, en nur tri multiplikoj, je la kosto de kelkaj aldonaj adicioj:

: *z2 = x1y1*
: *z0 = x0y0*
: *z1 = (x1 + x0)(y1 + y0) - z2 - z0*

aŭ

: *z1 = z2 + z0 - (x1 - x0)(y1 - y0)*

Elvolvante ĉiun el ĉi tiuj formuloj por *z1* eblas pruvi ke ĝi donas la saman valoron, por la unua:

: *z1 = (x1 + x0)(y1 + y0) - z2 - z0 =*
: *= (x1y1 + x1y0 + x0y1 + x0y0) - x1y1 - x0y0 = x1y0 + x0y1*

### Rikura apliko 
Se *n≥4*, ĉiu el la tri multiplikoj en baza paŝo de algoritmo de Karacuba ĝenerale laboras kun argumentoj kun *m≥2* ciferoj. Pro tio, ĉiu el tiuj produtoj povas esti komputita per rikuraj vokoj de la algoritmo de Karacuba. La rikuro povas esti aplikita ĝis kiam la nombroj estas tiel malgrandaj ke iliaj produtoj povas esti komputitaj senpere.

### Realigo 
En komputilo kiu kapablas senpere multipliki de 32-bitajn nombrojn kaj doni 64-bitan produton, oni ekzemple povas elekti *B = 232*. Tiam tamen por ĉiu el la sumoj *x1+x0* kaj *y1+y0* necesas je unu vorto pli multe.

Se sur ĉi tiu komputilo elekti *B = 231 = 2147483648* aŭ *B = 109*, kaj konservi ĉiun ciferon kiel apartan 32-bitan duuma vorto. Tiam ankaŭ la sumoj *x1+x0* kaj *y1+y0* povas esti konservitaj en la sama kvanto de 32-bitaj duumaj vortoj kiel *x1*, *x0*, *y1* kaj *y0*. Sed ĉi tio tamen povas doni problemojn dum la sekva pli ena paŝo de rikuro, ĉar la nombroj eble estos jam dekomence je 1 bito pli longaj, kaj pro ĉi tio la sumoj en la ena paŝo ne povos esti konservitaj en dezirata kvanto da vortoj.

Eblas preferi la formulon kun subtrahoj *x1-x0* kaj *y1-y0* kompari la nombrojn antaŭ subtraho, konservi la signumojn aparte, multipliki la absolutajn valorojn, kaj enkalkuli la signumojn poste, post fino de la pli ena paŝo de rikuro.

La rikuro povas esti aplikata ĝis kiam la nombroj estas ja nur 1 cifero longaj.

Kutime, algoritmo de Karacuba estas pli rapida ol simpla multipliko se la multiplikatoj estas pli grandaj ol 2320 ≈ 2·1096.

## Ekzemploj 
Oni komputu la produton de *x=1234* kaj *y=5678*. Estu *B=10* kaj *m=2* (aŭ povas esti *B=100* kaj *m=1*). Tiam:

: *1234 = 12 × 102 + 34*
: *5678 = 56 × 102 + 78*
: *z2 = 12 × 56 = 672*
: *z0 = 34 × 78 = 2652*
: *z1 = (12 + 34)(56 + 78) - z2 - z0 = 46 × 134 - 672 - 2652 = 2840*
La rezulto estas
: *xy = z2 × 102×2 + z1 × 102 + z0 = 672 × 10000 + 2840 × 100 + 2652 = 7006652*

Kvankam oni ĝenerale esperas ke unu paŝo de la algoritmo duonigas la longon de nombroj, ĉi tie de 4 al 2 ciferojn, tamen pro uzo de la formulo por *z1* kun sumoj *x1+x0* kaj *y1+y0*, ĉi tie aperis la multipliko 46 × 134 kun 3-cifera multiplikato.

----
Oni komputu la produton 12378456 × 25874215, kapablante senpere fari nur unu-ciferajn multiplikojn. Tiam estas *B=10*. Tiam necesas fari rikuron de profundo 3; en la ekstera paŝo de rikuro *m=4*; en la meza paŝo de rikuro *m=2*; en la plej ena paŝo de rikuro *m=1*. Oni uzu la formulon kun subtrahoj *x1-x0* kaj *y1-y0*.

En la ekstera paŝo de rikuro necesas komputi tri produtojn:
: 1237 × 2587
: 8456 × 4215
: (1237 - 8456) × (2587 - 4215) = 7219 × 1628

En la meza paŝo de rikuro, por komputi la produton 1237 × 2587 necesas komputi tri produtojn:
: 12 × 25
: 37 × 87
: (12 - 37) × (25 - 87) = 25 × 62

En la plej ena paŝo de rikuro, por komputi la produton 12 × 25 necesas komputi tri produtojn, kiuj eblas fari senpere:
: 1 × 2 = 2
: 2 × 5 = 10
: (1 - 2) × (2 - 5) = 1 × 3 = 3
kaj do 12 × 25 = 2 × 100 + (2 + 10 - 3) × 10 + 10 = 300.

Simile komputante en la ena paŝo de rikuro rezultas
: 37 × 87 = 3219
: 25 × 62 = 1550
kaj de ĉi ĉio 1237 × 2587 = 300 × 1002 + (300 + 3219 - 1550) × 100 + 3219 = 3000000 + 196900 + 3219 = 3200119.

Simile komputante en la meza paŝo de rikuro rezultas
: 1237 × 2587 = 3200119
: 8456 × 4215 = 35642040
: 7219 × 1628 = 11752532

De ĉi ĉio, fine

: 12378456 × 25874215 = 3200119 × 100002 + (3200119 + 35642040 - 11752532) × 10000 + 35652040 = 320011900000000 + 270896270000 + 35642040 = 320282831912040

La komputado bezonas entute 27 unu-ciferaj produtoj, anstataŭ 64 en la komuna metodo.

## Komplikeco 
La baza ŝtupo laboras por ĉiu bazo *B* kaj ĉiu *m*, sed la rikura algoritmo estas plej kompetenta se *m* estas egala al *n/2*, rondigita supren. Aparte, se *n=2k*, por iu entjero *k*, kaj la rikuro haltas nur kiam *n* estas 1, tiam la kvanto de unu-ciferaj multiplikoj estas *3k*, kio estas *nc* kie *c=log23*.

Pro tio ke oni povas etendi ĉiujn nombrojn kun nulaj ciferoj ĝis kiam ilia longo estas nenegativa entjera potenco de 2, la kvanto de rudimentaj multiplikoj por ĉiu *n* estas maksimume 3^{ \lceil\log_2 n \rceil} \leq 3 n^{\log_2 3}.

La adicioj, subtrahoj kaj movoj de ciferoj (multiplikoj per potencoj de *B*) en la unu baza paŝo prenas tempon proporcian al *n*. Ilia kosto en la plej suba paŝo de la rikuro estas proksimume proporcia el kosto de la multiplikoj. Estu ilia kosto *x* en la plej suba paŝo de la rikuro. Tiam ilia kosto estas *2x/3* en la pli supra paŝo de la rikuro, ĉar la nombroj en ĉiu apliko de la paŝo estas 2-foje pli longaj sed la kvanto de apartaj aplikoj estas 3-foje pli malgranda. Plu, ilia kosto estas *4x/9* en la sekva pli supra paŝo de la rikuro, *8x/27* en la sekva pli supra paŝo de la rikuro, ktp. Entuta kosto de adicioj, subtrahoj kaj movoj estas donita per la sumo de geometria progresio kaj estas *3x* kaj estas proksimume proporcia el kosto de la multiplikoj. Tiel ili ne pligrandigas la asimptotan komplikecon.

## Aliaj algoritmoj 
Ekzistas algoritmoj de multiplikado asimptote pli rapidaj ol la algoritmo de Karacuba, kvankam la pliaj rapideco estas atingata je kosto de komplikeco de algoritmo.

Algoritmo de Toom-Cook estas ĝeneraligo de la metodo kiu fendas la nombroj en *r* blokojn (anstataŭ 2). La tempo de komputado estas tiam *O(n1+ε)* kie *ε* povas esti pozitiva arbitre malgranda; tiel algoritmo de Toom-Cook estas asimptote pli rapida ĝeneraligo de algoritmo de Karacuba. Ekzemple se fendi la nombroj en 3 blokojn (anstataŭ 2), por multipliko de la nombroj tiam necesas 5 multiplikojn anstataŭ 9 en kutima multipliko, kaj la asimptota komplikeco estas do *Θ(nlog(5)/log(3))≈Θ(n1,465)*.

Ankoraŭ pli asimptote rapida algoritmo de multiplikado estas la algoritmo de Schönhage-Strassen, bazita sur la rapida konverto de Fourier. Ĝi estadas uzata por nombroj konsistantaj el dekoj da miloj da bitoj.

## Historio 
La kutima maniero der multipliko de du *n*-ciferaj nombroj postulas kvanton da rudimentaj operacioj asimptote proporcian al *n2*, aŭ *Θ(n2)*. En 1956, Andrej Kolmogorov (:ru:Андрей Николаевич Колмогоров) konjektis ke la klasika algoritmo estas asimptote optimala, kio signifas ke ĉiu algoritmo por la tasko devus postuli *Ω(n2)* rudimentajn operaciojn.

En aŭtuno de 1960, Kolmogorov organizis seminarion pri matematikaj problemoj en cibernetiko je la Moskva Ŝtata Universitato, kie li rakontis la *Ω(n2)* konjekton kaj la aliajn problemojn pri la komputa komplikeco. Por versaxjneco de la konjekto estis tio ke la longa multipliko estas konata por 4 jarmiloj, kaj se ekzistus pli rapida maniero, ĝi verŝajne jam estus trovita.

Tamen, en semajno, Anatolij Alekseevitĉ Karacuba (:ru:Анатолий Алексеевич Карацуба), tiam 23-jaraĝa studento, trovis la pli rapidan divido-kaj-regan algoritmo, tiel malpruvante la konjekton. Kolmogorov estis tre renversa pri la malkovro; li rakontis pri ĝi en la venonta konferenco de la seminario, kiu estis tiam finita.

La maniero estis publikigita en 1962, en la *Paperoj de la Unio de Soveta Socialisma Respublika Akademio de Sciencoj*. La artikolo estis skribita de Kolmogorova, eble en kunlaboro kun Yuri Petrovich Ofman, sed listis "A. Karacuba kaj Yu. Ofman" kiel la aŭtoroj. Karacuba eksciis pri la papero nur kiam li ricevis la represon de la eldonejo.

La algoritmo de Karacuba estas rimarkinda ekzemplo de la divido-kaj-rega algoritmo, aparte de duuma forkiĝanta algoritmo. La nomo 'dividu kaj regu' estis unua uzita por ĉi tiu maniero.

## Vidu ankaŭ 
* Algoritmo de Strassen - simila ideo por matrica multipliko
* Gaŭsa kompleksa multiplika algoritmo - simila ideo por multipliko de kompleksaj nombroj

## Referencoj 
* 

## Eksteraj ligiloj 
* 
* 
* Multiplika algoritmo de Karatsuba - TTT-bazita kalkulilo (Ĝenerala Publika GNU-Permesilo)
* Bernstein, D. J., "Multcifera multipliko por matematikistoj". Algoritmo de Karacuba kaj multaj aliaj multiplikaj algoritmoj.
* Algoritmo de Karacuba http://www.ccas.ru/personal/karatsuba/divcen.htm http://www.ccas.ru/personal/karatsuba/alg.htm
* http://saahiihii.com/storyPage.php?country=DK&page=DOCUMENT&section=EDUCATION&story=2&businessNo=1354&action=card 
* Multipliko de Karacuba
* http://ozark.hendrix.edu/~burch/proj/karat/comment1.html 
* Algoritmo de Karacuba 
* Ekzemplo de algoritmo de Karacuba en Delphi 
* http://212.cmc-msu.ru/files/kniga.html 
* http://numbers.computation.free.fr/Constants/Algorithms/representation.html
* http://www-math.uni-paderborn.de/mca/mult.html 
* http://www-2.cs.cmu.edu/~cburch/251/karat/
* http://www.cs.pitt.edu/~kirk/cs1501/animations/
* http://www.cs.princeton.edu/introcs/79crypto/Karatsuba.java.html 

Kategorio:Algoritmoj