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 $3n^{\log _{2}3}\approx 3n^{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 n² unu-ciferaj multiplikojn.

Se ekzemple n = 2¹⁰ = 1024, la kvanto de la unu-ciferaj multiplikoj ĉe algoritmo de Karacuba estas 3¹⁰ = 59049; kaj la kvanto de la unu-ciferaj multiplikoj ĉe klasika longa multipliko estas (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 = x₁B^m + x₀

y = y₁B^m + y₀

kie x₀ kaj y₀ estas malpli grandaj ol B^m. La produto estas tiam

xy = (x₁B^m + x₀)(y₁B^m + y₀) = z₂ B^2m + z₁ B^m + z₀

kie

z₂ = x₁y₁

z₁ = x₁y₀ + x₀y₁

z₀ = x₀y₀

Ĉi tiuj formuloj prezentas la klasikan longan multiplikan algoritmon kaj postulas kvar multiplikoj. La algoritmo de Karacuba estas la komputado de z₀, z₁ kaj z₂, en nur tri multiplikoj, je la kosto de kelkaj aldonaj adicioj:

z₂ = x₁y₁

z₀ = x₀y₀

z₁ = (x₁ + x₀)(y₁ + y₀) - z₂ - z₀

aŭ

z₁ = z₂ + z₀ - (x₁ - x₀)(y₁ - y₀)

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

z₁ = (x₁ + x₀)(y₁ + y₀) - z₂ - z₀ =

= (x₁y₁ + x₁y₀ + x₀y₁ + x₀y₀) - x₁y₁ - x₀y₀ = x₁y₀ + x₀y₁

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 = 2³². Tiam tamen por ĉiu el la sumoj x₁+x₀ kaj y₁+y₀ necesas je unu vorto pli multe.

Se sur ĉi tiu komputilo elekti B = 2³¹ = 2147483648 aŭ B = 10⁹, kaj konservi ĉiun ciferon kiel apartan 32-bitan duuma vorto. Tiam ankaŭ la sumoj x₁+x₀ kaj y₁+y₀ povas esti konservitaj en la sama kvanto de 32-bitaj duumaj vortoj kiel x₁, x₀, y₁ kaj y₀. 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 x₁-x₀ kaj y₁-y₀ 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 2³²⁰ ≈ 2·10⁹⁶.

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 × 10² + 34

5678 = 56 × 10² + 78

z₂ = 12 × 56 = 672

z₀ = 34 × 78 = 2652

z₁ = (12 + 34)(56 + 78) - z₂ - z₀ = 46 × 134 - 672 - 2652 = 2840

La rezulto estas

xy = z₂ × 10^2×2 + z₁ × 10² + z₀ = 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 z₁ kun sumoj x₁+x₀ kaj y₁+y₀, ĉ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 x₁-x₀ kaj y₁-y₀.

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 × 100² + (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 × 10000² + (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=2^k, por iu entjero k, kaj la rikuro haltas nur kiam n estas 1, tiam la kvanto de unu-ciferaj multiplikoj estas 3^k, kio estas n^c kie c=log₂3.

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 3n^{\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

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(n^1+ε) 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 Θ(n^{log(5)/log(3)})≈Θ(n^1,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 n², aŭ Θ(n²). En 1956, Andrej Kolmogorov (ru:Андрей Николаевич Колмогоров) konjektis ke la klasika algoritmo estas asimptote optimala, kio signifas ke ĉiu algoritmo por la tasko devus postuli Ω(n²) rudimentajn operaciojn.

En aŭtuno de 1960, Kolmogorov organizis seminarion pri matematikaj problemoj en cibernetiko je la Moskva Ŝtata Universitato, kie li rakontis la Ω(n²) 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ŭ

• Algoritmo de Strassen - simila ideo por matrica multipliko
• Gaŭsa kompleksa multiplika algoritmo - simila ideo por multipliko de kompleksaj nombroj

Referencoj

• Карацуба А., Офман Ю. - 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

• A. A. Karacuba (1995). The Complexity of Computations - La komplikeco de komputadoj. Proceedings of the Steklov Institute of Mathematics - Paperoj de la Steklov-a Instituto de matematiko 211 169–183.
• Eric W. Weisstein, Multipliko de Karacuba en MathWorld.
• 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 [1] [2]
• [3]
• Multipliko de Karacuba
• [4] Arkivigite je 2016-03-13 per la retarkivo Wayback Machine
• Algoritmo de Karacuba Arkivigite je 2007-10-31 per la retarkivo Wayback Machine
• Ekzemplo de algoritmo de Karacuba en Delphi Arkivigite je 2007-09-28 per la retarkivo Wayback Machine
• [5] Arkivigite je 2022-01-03 per la retarkivo Wayback Machine
• [6]
• [7] Arkivigite je 2016-04-17 per la retarkivo Wayback Machine
• [8]
• [9]
• [10] Arkivigite je 2007-01-25 per la retarkivo Wayback Machine