Karatsuba-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 17. lokakuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 13 muokkausta .

Karatsuba kertolasku on nopea kertolaskumenetelmä, jonka avulla voit kertoa kaksi n - numeroista lukua bitin laskennallisen monimutkaisuuden avulla :

T(n)=O(n^{\log _{2}3}),\quad \log _{2}3=1{,}5849\ldots

Sen keksi Anatoli Karatsuba vuonna 1960 . Se on historiallisesti ensimmäinen kertoalgoritmi, joka ylittää triviaalin asymptoottisessa kompleksisuudessa [1] [2] [3] [4] .

Historia

Vuonna 1960 Andrei Kolmogorov piti seminaarin kybernetiikan matemaattisista ongelmista. Yksi seminaarissa käsitellyistä tehtävistä oli kahden bitin kokonaislukujen kertominen . Tärkein tunnettu kertolaskutapa tuolloin oli kertominen ”sarakkeessa”, joka algoritmisesti toteutettuna vaati alkeisoperaatioita (yksinumeroisten lukujen yhteen- tai kertolaskuja). Kolmogorov oletti, että kertominen "sarakkeessa" on optimaalinen algoritmi kahden luvun kertomiselle siinä mielessä, että minkä tahansa kertolaskumenetelmän ajoaika on vähintään suuruusluokkaa. "Hypoteesin " uskottavuutta osoitti se, että "sarakkeessa" kertomismenetelmä on ollut tunnettu ainakin neljä vuosituhatta, ja jos olisi ollut nopeampi kertolaskumenetelmä, niin se olisi luultavasti jo löydetty. Kuitenkin viikkoa myöhemmin 23-vuotias Anatoli Karatsuba [5] [6] [7] [8] ehdotti uutta menetelmää kaksinumeroisten lukujen kertomiseksi käyntiajan arviolla ja kumosi näin "hypoteesin ". $n$ $O(n^{2})$ $n^{2}$ $n^{2}$ $n$ $O(n^{\log _{2}3})$ $n^{2}$

Karatsuba-menetelmä kuuluu " jakaa ja hallitse " -algoritmeihin, samoin kuin algoritmit, kuten binäärihaku , pikalajittelu jne. Karatsuba-menetelmässä käytetyt rekursiiviset pelkistyskaavat tunsivat Charles Babbage , joka ei kuitenkaan kiinnittänyt huomiota mahdollisuus käyttää vain kolmea rekursiivista kertolaskua neljän sijasta [9] .

Menetelmän kuvaus

Kaksibittiset luvut voidaan esittää muodossa , , missä ; . $n$ ${\näyttötyyli a+b}$ $cx+d$ ${\displaystyle x=2^{\lceil {n/2}\rceil ))$ ${\displaystyle a,b,c,d<2^{\lceil {n/2}\rceil ))$

Kertominen ( bittisiirto ) ja yhteenlasku tehdään vakioajassa . Siksi kertolaskuongelma rajoittuu polynomin kertoimien laskemiseen . Identiteettiä käyttämällä ${\displaystyle 2^{\lceil {n/2}\rceil ))$ $O(1)$ ${\näyttötyyli (ax+b)(cx+d)}$

{\väri {vihreä}(a+b)(c+d)}={\väri {punainen}ac}+{\väri {tummaväri}(ad+bc)}+{\väri {sininen}bd }\ ,

tämä polynomi voidaan esittää muodossa

(ax+b)(cx+d)={\väri {punainen}ac}x^{2}+{\väri {tummaväri}(ad+bc)}x+{\color {blue}bd}=

={\väri {punainen}ac}x^{2}+{\väri {tummarange}{\Big (}}{{\color {green}(a+b)(c+d)}-{ \väri {punainen}ac}-{\väri {sininen}bd}}{\väri {tummaväri}{\Big )))x+{\color {blue}bd}\ .

Viimeinen lauseke sisältää kolme -numeroisten lukujen tuotetta. Jos laskemme kukin niistä saman kaavion mukaan, saamme algoritmin, jossa on rekursiivinen arvio ajoajasta $\left({\left\lceil {\frac {n}{2}}\right\rceil +1}\oikea)$

T(n)=3T\left({\frac {n}{2}}\right)+O(n)=O(n^{\log _{2}3})\ .

Vertailun vuoksi samanlainen algoritmi, joka suorittaa erikseen kaikki neljä kertolaskua , , , vaatisi tavanomaisen ajan $ac$ ${\näyttötyylimainos}$ $eKr$ $bd$

T(n)=4T\left({\frac {n}{2}}\right)+O(n)=O(n^{\log _{2}4})=O(n^ {2})\ .

Esimerkkejä

Esityksen helpottamiseksi käytämme desimaalijärjestelmää, eli muodon polynomin argumentteja . Numeroiden värimerkintä ei liity edelliseen osaan, vaan osoittaa vain, mistä numerosta yksi tai toinen osa on erotettu. ${\displaystyle x=10^{k))$ ${\displaystyle x=2^{k))$

Lasketaan : ${\color {red}1213}\cdot {\color {blue}2311}$

huomioi ja laske : ${\väri {punainen}12}+{\väri {punainen}13}=25,\ {\väri {sininen}23}+{\väri {sininen}11}=34$ ${\displaystyle {\color {darkorange}25}\cdot {\color {magenta}34))$
- Huomaa, että laskemme ${\color {darkorange}2}+{\color {darkorange}5}=7,\ {\color {magenta}3}+{\color {magenta}4}=7$ $7\cdot 7=49$
- laskea ${\color {darkorange}2}\cdot {\color {magenta}3}=6$
- laskea ${\color {darkorange}5}\cdot {\color {magenta}4}=20$
- summaamalla tulokset, saamme sen ${\color {darkorange}25}\cdot {\color {magenta}34}=6\cdot 10^{2}+(49-6-20)\cdot 10+20=850$
laske näin : ${\color {red}12}\cdot {\color {blue}23}$ ${\color {darkorange}12}\cdot {\color {magenta}23}$
- Huomaa, että laskemme ${\color {darkorange}1}+{\color {darkorange}2}=3,\ {\color {magenta}2}+{\color {magenta}3}=5$ $3\cdot 5=15$
- laskea ${\color {darkorange}1}\cdot {\color {magenta}2}=2$
- laskea ${\color {darkorange}2}\cdot {\color {magenta}3}=6$
- summaamalla tulokset, saamme sen ${\color {darkorange}12}\cdot {\color {magenta}23}=2\cdot 10^{2}+(15-2-6)\cdot 10+6=276$
laske näin : ${\color {red}13}\cdot {\color {blue}11}$ ${\color {darkorange}13}\cdot {\color {magenta}11}$
- Huomaa, että laskemme ${\color {darkorange}1}+{\color {darkorange}3}=4,\ {\color {magenta}1}+{\color {magenta}1}=2$ $4\cdot 2=8$
- laskea ${\color {darkorange}1}\cdot {\color {magenta}1}=1$
- laskea ${\color {darkorange}3}\cdot {\color {magenta}1}=3$
- summaamalla tulokset, saamme sen ${\color {darkorange}13}\cdot {\color {magenta}11}=1\cdot 10^{2}+(8-1-3)\cdot 10+3=143$
summaamalla tulokset, saamme sen ${\color {red}1213}\cdot {\color {blue}2311}=276\cdot 10^{4}+(850-276-143)\cdot 10^{2}+143=2803243$

Muistiinpanot

↑ Käytännössä algoritmista tulee perinteistä kertolaskua tehokkaampi kerrottaessa lukuja, joiden pituus on luokkaa satoja binäärilukuja (kymmeniä desimaalilukuja); pienemmillä luvuilla algoritmi ei tarjoa merkittävää etua, koska enemmän tarvittavia yhteen-, vähennys- ja siirtoja kuin naiivissa algoritmissa.
↑ S. A. Gritsenko, E. A. Karatsuba, M. A. Korolev, I. S. Rezvyakova, D. I. Tolev, M. E. Changa. Anatoli Aleksejevitš Karatsuban tieteelliset saavutukset // Matematiikka ja informatiikka, 1, Anatoli Aleksejevitš Karatsuban syntymän 75-vuotispäivänä, Sovrem. prob. Mat., 16, MIAN, M., 2012, 7–30.
↑ Karatsuba E. A. Fast Algorithms and the BEE Method Arkistoitu 4. marraskuuta 2012 Wayback Machinessa , 2008.
↑ Alekseev V. B. Karatsuba-menetelmästä lukujen nopeaan kertomiseen nopeisiin algoritmeihin diskreeteille funktioille // Tr. MIAN. - 1997. - T. 218 . - S. 20-27 .
↑ Karatsuba A., Ofman Yu. Moniarvoisten lukujen kertominen automaateilla // Neuvostoliiton tiedeakatemian raportit. - 1962. - T. 145 , nro 2 .
↑ Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen (saksa) // Elektronische Informationsverarbeitung und Kybernetik. - 1975. - Bd. 11 .
↑ Karatsuba A. A. Laskennallinen monimutkaisuus // Tr. MIAN. - 1995. - T. 211 . — S. 186–202 .
↑ Knut D. Ohjelmoinnin taito. - 3. painos - M .: Williams , 2007. - V. 2. Saadut algoritmit. — 832 s. — ISBN 0-201-89684-2 .
↑ A. Shen . Gaussin kertolaskutemppu? // Matemaattinen valaistuminen . - 2019. - T. 24 . (Venäjän kieli)

Linkit

Lukuteoreettiset algoritmit
Yksinkertaisuustestit	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saksi Nightingale - Strassen
Alkulukujen löytäminen	Iterointi jakajien yli Eratosthenesin seula Atkinin seula Seula Sundarama
Faktorisointi	Iterointi jakajien yli Fermat menetelmä p −1 Pollardin menetelmä Pollardin ρ-algoritmi Lehmannin menetelmä Elliptisen käyrän menetelmä (Lenstran algoritmi) Dixonin algoritmi Neliömäinen seula
Diskreetti logaritmi	Gelfond-Shanks -algoritmi Polig-Hellman-algoritmi Pollardin ρ-menetelmä Pollardin kenguru-algoritmi Adlemanin algoritmi COS-algoritmi
GCD:n löytäminen	Eukleideen algoritmi Kehittynyt algoritmi Binäärinen algoritmi
Modulo-aritmetiikka	Montgomeryn algoritmi Kiinan jäännöslause
Lukujen kerto- ja jakolasku	Karatsuba-algoritmi Toom-Cook-algoritmi Schönhage-Strassen-algoritmi Fuhrer-algoritmi Harvey-van der Hoeven-algoritmi Burnickel-Ziegler-algoritmi
Neliöjuuren laskeminen	Tonelli-Shanks-algoritmi Berlekamp-Rabin-algoritmi