- I-Karatsuba yehlisa ukuphindaphindeka okukhulu ukusuka koku-4 kuye koku-3 ngokuhlukanisa nokunqoba, yehlisa ubunkimbinkimbi ku-Θ(n^{1,585}).
- Indlela isuselwe ekuboleni u-x kanye no-y kusisekelo B, ukuhlanganisa u-z2, z0 kanye no-(x1+x0)(y1+y0), kanye nokuqamba kabusha ngamandla ka-B.
- Ngokomlando, yachitha umcabango we-Kolmogorov futhi yavula indlela ye-Toom-Cook ne-Schönhage-Strassen yafinyelela ku-O(n log n) ngo-2019.
Uma siphindaphinda izinombolo ezincane, singakwenza nje emakhanda ethu futhi kuphuma cishe ngaphandle kokucabanga; ngezinombolo ezinkulu, izinto ziyashintsha futhi sivame ukusebenzisa iphepha, umshini wokubala, noma umtapo wesofthiwe. Ukuphindaphinda kwenani elikhulu akulona nje ilukuluku: kuyisisekelo sokubethela, i-algebra yekhompyutha, kanye nezinhlelo eziningi zokubala.
Kulesi simo, kuvela i-algorithm kaKaratsuba, umqondo omuhle kakhulu onciphisa inani lokuphindaphinda elidingekayo ngokushintsha okunye ngokwengeza nokushintsha. Icebo lokuhlukanisa nokunqoba lehlisa ubunzima bendlela yakudala, engama-quadratic, ibe amandla aphansi, livula umnyango wokuphindaphinda okusheshayo kakhulu ngezinga elikhulu.
Kungani ukuphindaphinda izinto ngokushesha kanye nemikhawulo yendlela yakudala
Indlela yesikole yendabuko (ukuphindaphinda kwekholomu) kulula ukuyiqonda: siphindaphinda inombolo ngayinye yenombolo eyodwa ngenombolo ngayinye yenye bese sihlanganisa izingxenye ezihambisana nendawo. Ngezinombolo zezinombolo ezingu-n ngethemu ngayinye, lokhu kusiphoqa ukuthi senze cishe ukuphindaphinda okungu-^2 okuyisisekelo, ngaphezu kokwengezwa okuningi.
Ngokwesiko, inqubo ejwayelekile idinga inani lemisebenzi ehambisana ne-an^2, okungukuthi, i-Θ(n^2) ku-asymptotic notation. Uma sibiza i-c1 isikhathi sokuphindaphinda ngakunye okuyisisekelo kanye ne-c2 isikhathi sokwengeza ngakunye, isikhathi esimaphakathi singalinganiswa nge-c1·n^2 + c2·n^2. Njengoba ukuphindaphinda kuvame ukudla isikhathi esiningi kunokwengeza, ku-n enkulu kulinganiselwa kahle nge -c1·n^2.
Ukuze sikubeke ngezinombolo, ake sicabangele u-4572 × 3169 sisebenzisa indlela yendabuko. Zombili zinezinombolo ezine, ngakho-ke kuzoba nemikhiqizo eyisisekelo engu-16 kanye nenani elifanayo lezibalo zokuqoqa izingxenye. Le ndlela yokukhula kwe-quadratic iba nzima kakhulu njengoba silinganisa, futhi yiwona kanye umkhawulo ama-algorithms asheshayo azama ukuwuqeda.
Ngokomlando, kwakucatshangwa ukuthi kwakungekho ndawo enkulu yokuthuthukisa. Umbono wokuthi "ukube kukhona okungcono, ngabe sikutholile manje" waqhubeka amashumi eminyaka. Kodwa-ke, umlando washintsha kakhulu emhlanganweni eMoscow ngo-1960.
Umlando: kusukela ekuqageleni kukaKolmogorov kuya ekutholakaleni kweKaratsuba
Ngawo-50, u-Andrey N. Kolmogorov wazama ukuphikisana ngokuthi i-algorithm yokuphindaphinda yakudala yayingcono kakhulu ngokwezimpawu; ngokwezobuchwepheshe, ukuthi noma iyiphi indlela yokuphindaphinda yayidinga, esimweni esibi kakhulu, imisebenzi ye -Ω(n^2) . Ekwindla ka-1960, wahlela iseminari nge-cybernetics eMoscow State University lapho abelana khona ngalokhu kucabanga kanye nezinye izinselele zobunzima bokubala.
Ngemva kwesonto elilodwa nje, u-Anatoly Karatsuba, owayengumfundi ngaleso sikhathi (ngokusho kwemithombo ehlukene, eneminyaka engu-23 noma engu-25 ubudala ), wethula indlela yokuhlukanisa nokunqoba eyayisebenza ngokuphindaphindeka ku -Θ(n^{log_2 3}) , okungukuthi, nge-exponent ≈ 1,585. Lokhu kwaguqula ukuqagela kukaKolmogorov, futhi njengoba indaba iqhubeka, kwamshiya edumele kakhulu; yena ngokwakhe waveza umphumela esimisweni esilandelayo nesokugcina seminari.
Lo msebenzi wanyatheliswa ngo-1962 kuyi-Proceedings of the USSR Academy of Sciences. Lesi sihloko, okungenzeka ukuthi sabhalwa nguKolmogorov ngokwakhe (mhlawumbe noYuri Ofman), sabhala u-A. Karatsuba no-Yu. Ofman njengababhali . Ngokuthakazelisayo, uKaratsuba wezwa ngalo mbhalo kuphela lapho ethola ikhophi yalo magazini; wayengahilelekile enkambisweni yokuhlela. Kusukela ngo-1963 kuqhubeke, lapho usuhunyushiwe, lo msebenzi wabangela uchungechunge lwentuthuko ekuphindaphindeni nasekudluleni kwawo.
Ukuzivikela kukaKolmogorov kokuqala, okunethonya elikhulu ngenxa yodumo lwakhe, kwakuwele ogibeni olunengqondo: impikiswano evela ekungazini . Ukuntuleka kobufakazi be-algorithm engcono akusho ukuthi umuntu wayengeke abe khona. UKaratsuba wafakazela okuphambene nomqondo olula noma onamandla.
I-algorithm ye-Karatsuba, yachaza
Umqondo oyinhloko ukuhlakaza ama-operand nokuhlanganisa kabusha ngobuhlakani imikhiqizo engaphelele. Vumela u-B abe isisekelo (isisekelo sendawo lapho sibhala khona izinombolo) bese sithatha izinombolo ezimbili zezinombolo ezingu-n u-x no-y. Sikhetha inombolo ephelele u-m eno-0 < m < y bese sihlukanisa inombolo ngayinye ibe "izingxenye" ezimbili zobukhulu obufanayo:
x = x 1 ·B^m + x 0 kanye no-y = y 1 ·B^m + y 0 , kanye no-x 0 , y 0 < B^m. Uma sandisa umkhiqizo, sithola:
xy = (x 1 ·B^m + x 0 )(y 1 ·B^m + y 0 ) = z 2 ·B^{2m} + z 1 ·B^m + z 0 , lapho z 2 = x 1 y 1 , z 1 = x 1 y 0 + x 0 y 1 , z 0 = x 0 y 0 . Ukwandiswa okuqondile kusebenzisa ukuphindaphinda okungu-4 “okukhulu”.
UKaratsuba waphawula ukuthi u-z1 angabalwa ngaphandle kokuphindaphinda okuhlanganisiwe. Kwanele ukubala imikhiqizo emithathu: u-z2 = x1y1 , u-z0 = x0y0 , u-yt = ( x1 + x0 ) ( y1 + y0 ) . Bese u-z1 = t − z2 − z0 . Ngalokhu , izindleko zehla kusukela ekuphindaphindeni okungu-4 kuya ekuphindaphindeni okungu-3 kuphela ( kanye nokwengezwa nokususa, okushibhile), bese siphinda sibhale u-xy njengakuqala.
Lesi sinyathelo esiyisisekelo sisebenza kunoma yisiphi isisekelo u-B nanoma yimuphi u-m, yize i-algorithm ephindaphindayo isebenza kangcono uma u-m ≈ n/2 (ukuqongelela). Uma u-n enamandla amabili , futhi simisa ukuphindaphinda lapho u-n=1, inani lemikhiqizo enezinombolo eyodwa lingu-3^k uma u-n=2^k, okungukuthi, u-n^c lapho u-c = u-log₂ ( 3). Ngaphezu kwalokho, singanweba ngo-zero abaholayo siye emandleni alandelayo amabili, ngakho-ke inani lokuphindaphinda okuyisisekelo liyanelisa u-3^{log₂ ( n)} ≤ 3^{log₂ ( 3)}.
Kunezindlela ezinqamulelayo ezincane: uma, isibonelo, u-y 1 = 0 (ingxenye ephezulu ka-y ingu-zero), imikhiqizo emibili yanele njengoba u-z 2 = 0, u-z 0 = x 0 y 0 , u-z 1 = x 1 y 0. Lezi zimo eziwohlokayo zivela ekupheleni kokuphindaphinda futhi zinciphise umsebenzi owengeziwe.
Inzuzo ebalulekile esebenzayo ukuthi izibalo, umehluko, kanye nokushintsha kwamandla kwe-B kuqondile ku-n; isisindo sazo esihlobene siyancipha njengoba u-n ekhuphuka. Ekubhalweni okuphindaphindiwe , uma u-t(n) kuyindleko iyonke yokuphindaphinda izinombolo ezimbili ze-n, singabhala u-t(n) = 3·t(⌈n/2⌉) + c·n + d kuma-constant c no-d. Sisebenzisa i-Master Theorem, sithola i-asymptotic bound t(n) = Θ(n^{log 3 / log 2}).
Ubunkimbinkimbi, isibonelo esinemininingwane kanye nokuqaliswa okusebenzayo
Ake sibheke isibonelo esiqondile ngesisekelo 10 ukuze sibone ukusebenza kwemishini. Thatha u-x=1234 kanye no-ey=5678. Sikhetha u-B=10 kanye no-ym=2, ngakho-ke u-1234 = 12·10^2 + 34 kanye no -5678 = 56·10^2 + 78. Sibala imikhiqizo emithathu "emikhulu" ye-Karatsuba: z2 = 12×56 = 672, z0 = 34×78 = 2652, kanye no-yt = (12+34)(56+78) = 46×134 = 6164. Bese u-z1 = t − z2 − z0 = 6164 − 672 − 2652 = 2840.
Manje sidinga ukuhlela kabusha: xy = z 2 ·B^{2m} + z 1 ·B^m + z 0 = 672·10^4 + 2840·10^2 + 2652 = 7.006.652 . Ngokuphindaphindwa okuyinhloko okuthathu, kanye nokwengezwa kanye nokushintsha kwedesimali, sifika emphumeleni ofanayo nendlela yakudala eneziphindaphindo ezine ezinkulu.
I-algorithm isetshenziswa ngokuphindaphindiwe: umkhiqizo ngamunye u-z2 , u-z0 , kanye no-t , nawo, ungabalwa kusetshenziswa i-Karatsuba lapho ama-operand esemakhulu. Ukuphindaphinda kuyama lapho izinombolo zincane ngokwanele ukuthi ziphindaphindwe ngqo (indlela yesikole noma ukuphindaphinda kwe-CPU yomdabu).
Ngokombono wokwakha, kunezinketho ezilula kakhulu zesisekelo B. Emshinini one-multiplier ephelele ye-ALU engu-32×32-bit, ukukhetha i-B=2^31=2.147.483.648 noma i-B=10^9=1.000.000.000 kuvumela "inombolo" ngayinye ukuthi igcinwe egameni elingu-32-bit. Ngalezi zisekelo , izibalo zefomu x1 + x0 noma y1 + y0 azidingi inombolo eyengeziwe yokuthwala (njengase-adder yokulondoloza ukuthwala), futhi singasebenzisa i-recursion kuze kube secaleni lesisekelo "senombolo" eyodwa.
Kuhle ukukhumbula ukuthi, ngamanani amancane ka-n, i-overhead yokwengeza kanye nokunyakaza kungenza i-Karatsuba ihambe kancane kunendlela yekholomu. Iphuzu elihambayo lincike epulatifomu kanye nomongo: ama-cache, ama-latencies, ukusetshenziswa okuthile, njll. Eminye imithombo ibeka inzuzo ye-Karatsuba kuma-operand amakhulu kakhulu (ngokulandelana okungu-2^320 ≈ 2×10^96 noma ngaphezulu), kuyilapho empeleni, imitapo yolwazi yanamuhla ivame ukusebenza kusenesikhathi kakhulu ngosayizi omaphakathi; noma kunjalo, kuhlale kunomkhawulo odlula lapho uba wusizo khona.
Ngokwezibalo, izindleko eziphelele zanelisa ubudlelwano bokuphindeka t(n) = 3·t(⌈n/2⌉) + c·n + d , ikhambi layo elingenazimpawu lingu-Θ(n^{log 3 / log 2}) ≈ Θ(n^{1,585}). Ukuthuthuka ngaphezu kuka-Θ(n^2) akusikho okulinganiselwe: ngokuphinda kabili u-n, umsebenzi ukhuphuka ngesici esingu-≈ 2^{1,585} esikhundleni sika-4. Futhi uma sidinga ukuphoqa u-n ukuthi abe amandla amabili, sidinga nje ukumboza ngo-zero ngakwesobunxele; inani lokuphindaphinda okuyisisekelo lilinganiselwe ngu-3^{⌈log 2 n⌉} ≤ 3·n^{log 2 3}.
Ngale kukaKaratsuba , intuthuko ayizange ime. UToom noCook (1966) bahlanganisa lo mbono futhi behlisa umkhawulo, kwathi ngo-1971 uSchönhage noStrassen bethula i-algorithm esekelwe ku-Fast Fourier Transform (FFT) ukuze baqhubeke nokucindezela imikhawulo. Laba babhali baphakamise nokuthi umkhawulo ophansi ongenzeka wokuphindaphinda wawungowoku-oda n log n.
Emashumini eminyaka kamuva, ngo-2019, uDavid Harvey noJoris van der Hoeven bethula indlela efinyelela i -O(n log n) ngesikhathi, futhi ithembele ku-FFT kodwa yandise ibe yizilinganiso eziyi-1729. Nakuba inzuzo esebenzayo uma iqhathaniswa nezinye izindlela ezifanayo ingabi nkulu ngaso sonke isikhathi futhi idinga ubukhulu obukhulu ukuze ikhanye ngempela, impumelelo yemfundiso iyamangalisa: umkhawulo ocatshangelwayo usufinyelelwe.
Uma uzibuza ukuthi kungani iKaratsuba ingafundiswa esikoleni samabanga aphansi, impendulo ilula: ngezinombolo ezincane, indlela yakudala ingcono kakhulu ekusebenzeni, futhi imali eningi yeKaratsuba ayikuvumeli lokho. Kodwa-ke, imitapo yolwazi emikhulu yezinombolo ezindimini zokuhlela iyayisebenzisa; empeleni, ivame ukusebenzisa ama-algorithms amaningana (akudala, iKaratsuba, iToom-Cook, i-FFT, njll.) futhi ikhetha ngendlela efaneleke kakhulu ngokusekelwe kusayizi. Njengoba ukuphindaphinda kuqhubekela kuma-operand amancane, bangakwazi ngisho "ukushintsha amagiya" futhi baqede ngokuphindaphinda okujwayelekile.
Ukuze kuqhutshekwe nocwaningo, kunemithombo ebalulekile yokubhekisela: Knuth, The Art of Computer Programming, Vol. 2 , izihloko zobuchwepheshe ezifana neKaratsuba–Ofman's, ama-compendium afana neMathWorld kanye namanothi kaDJ Bernstein mayelana nokuphindaphinda kwamadijithi amaningi, kanye nezinsiza eziwusizo (izibali eziku-inthanethi) ezisebenzisa iKaratsuba kanye nezinhlobo ezahlukene.
Izinkomba nokufunda okunconyiwe
- Karacuba AA Berechnungen und die Kompliziertheit von Beziehungen. I-electron. Ulwazisverarb. I-Kybernetik 11, 603–606 (1975).
- Knuth DE I-Art of Computer Programming, Vol. 2. Addison–Wesley (1969).
- I-MathWorld: Ukuphindaphinda kwe-Karatsuba (ngesiNgisi)
- Bernstein, DJ Ukuphindaphinda kwamadijithi amaningi kochwepheshe bezibalo. Ukubuyekezwa kweKaratsuba nezinye izindlela.
- Ukuphindaphinda kwe-Karatsuba kuma-Algorithms asheshayo kanye ne-FEE; I-Karatsuba isebenzisa izikwele zomehluko; izibali eziku-inthanethi eziyisebenzisayo.
Umqondo wale ndaba ukabili: ngakolunye uhlangothi, umqondo ohlakaniphile ungagumbuqela izinkolelo ezijulile; ngakolunye uhlangothi, ukuthuthuka kusuka ku-Θ(n^2) kuya ku-Θ(n^{1,585}) kwanele ukwenza umehluko obonakalayo ezinkingeni zomhlaba wangempela ngezinombolo ezinkulu. Njengoba izinhlobo zesimanje zifinyelela ku-O(n log n) kanye nezinhlelo ezikhetha i-algorithm efaneleke kakhulu ngokusekelwe kusayizi, isimo samanje sokuphindaphindwa kwezinombolo eziphelele sicebile futhi sisebenza kahle kunanini ngaphambili.