Algoritmo de Karacuba

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

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[redakti | redakti fonton]

La baza paŝo[redakti | redakti fonton]

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 xy, 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

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[redakti | redakti fonton]

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[redakti | redakti fonton]

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 = 2147483648B = 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[redakti | redakti fonton]

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[redakti | redakti fonton]

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 apartoj 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[redakti | redakti fonton]

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[redakti | redakti fonton]

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-jar-aĝ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ŭ[redakti | redakti fonton]

Referencoj[redakti | redakti fonton]

  • Карацуба А., Офман Ю. - A. Karacuba kaj Ju. Ofman (1962). Умножение многозначных чисел на автоматах - Multipliko de mult-ciferaj nombroj per aŭtomatoj. Доклады Академии Наук СССР - Paperoj de la Unio de Soveta Socialisma Respublika Akademio de Sciencoj 145 293-294.

Eksteraj ligiloj[redakti | redakti fonton]