Kokonaislukukertainen algoritmi

Kertolaskualgoritmit laskemiseen käytetty tuloksen kertomisen .

Graafisesti kyse on kertojan × moninkertaisen suorakulmion muuttamisesta viivaksi pitämällä elementtien lukumäärä.

Luku 2 perustuva kertolasku

Tämäntyyppinen kertolasku käyttää vain summaamista ja kertomista tai jakamista 2: lla. Se ei vaadi tuntemusta kertotaulukkoon (muu kuin kertolasku 2: lla).

• Kertomistekniikka muinaisessa Egyptissä
• (muunnos) Venäjän kertotekniikka

Kertolasku desimaalimerkintöjen perusteella

Tämäntyyppinen kertolasku käyttää numeroiden desimaalilaskua ja vaatii sinua kertomaan ensimmäisen numeron kukin toisen numerolla. Se edellyttää yhden numeron kertotaulukon tuntemista toiselle. Vuosien varrella on kuitenkin hyväksytty useita erityyppisiä säännöksiä.

• Kertotekniikka muinaisessa Kiinassa
• Liukukerroin tekniikka
• Kateuden avulla lisääntymisen tekniikka
• Käsi-kertotekniikka ( kertotaulukon kanssa )
• Graafinen tekniikka kertomalla laskemalla leikkauspisteet (ei vaadi tuntemusta kertotaulukkoon).

Nopea kertolasku

Suurin osa edellisillä sivuilla kuvatuista menetelmistä vaatii kertomisen jokaisen numeron kertomisen kerroksen jokaisella numerolla. Jos näillä kahdella luvulla on numeroita, se vaatii tuotteita: sanomme, että laskennan monimutkaisuus on neliöaikaa tai . ei{\ displaystyle n}ei2{\ displaystyle n ^ {2}}O(ei2){\ displaystyle {\ mathcal {O}} (n ^ {2})}

Tietokoneiden tulo mahdollisti ja vaati nopeammien algoritmien kehittämistä suurille lukumäärille. Ensimmäisillä havaittiin muodon monimutkaisuus , jossa a on positiivinen todellinen, tiukasti alle 1. Arnold Schönhage ja Volker Strassen ovat arvelleet vuonna 1971, että Kahden kokonaisluvun tulolla on monimutkaisuus , toisin sanoen että aikakompleksilla on algoritmi, eikä yhdelläkään ole parempaa. Paras monimutkaisuus on ollut vuodesta 2019 lähtien vuonna 2019, mutta sitä ei voida käyttää käytännössä, koska se saavutetaan vain erittäin suurille määrille, enemmän kuin alkuperäisessä viestissä. Mitään algoritmia, jolla olisi parempi monimutkaisuus kuin oletettu, ei löydy, ja Schönhagen ja Strassenin oletusten oletetaan olevan edelleen voimassa vuonna 2019. Kaikki alla olevat algoritmit kehitettiin vuoden 1960 jälkeen. O(ei1+klo){\ displaystyle O (n ^ {1 + a})}O(eiHirsi⁡ei){\ displaystyle O (n \ log n)}O(eiHirsi⁡ei){\ displaystyle O (n \ log n)}2172912{\ displaystyle 2 ^ {1729 ^ {12}}}

• Karatsuban algoritmi  : monimutkaisuus joko suunnilleen  ; Vuonna 1962 suunniteltu se on ensimmäinen algoritmi, jonka monimutkaisuus on toissijainen;O(eiHirsi2⁡(3)){\ displaystyle {\ mathcal {O}} (n ^ {\ log _ {2} (3)})}O(ei1,585){\ displaystyle {\ mathcal {O}} (n ^ {1 585})}
• Toom- Cook- tai "Toom3" -algoritmi: monimutkaisuus sisällä tai suunnilleen  ;O(eiHirsi3⁡(5)){\ displaystyle {\ mathcal {O}} (n ^ {\ log _ {3} (5)})}O(ei1,465){\ displaystyle {\ mathcal {O}} (n ^ {1 465})}
• Schönhage-Strassen-algoritmi , menetelmä käyttäen nopeaa Fourier-muunnosta  : monimutkaisuus sisään , suunniteltu vuonna 1971;O(ei⋅Hirsi⁡ei⋅Hirsi⁡Hirsi⁡ei){\ displaystyle {\ mathcal {O}} (n \ cdot \ log n \ cdot \ log \ log n)}
• Fürerin algoritmi  : monimutkaisuus , jossa merkitään iteroitua logaritmia ja joka on ehdottomasti suurempi kuin 1, suunniteltu vuonna 2007;O(eiHirsi⁡eiKO(Hirsi∗⁡ei)){\ displaystyle {\ mathcal {O}} (n \ log nK ^ {O (\ log ^ {*} n)})}Hirsi∗⁡ei{\ displaystyle \ log ^ {*} n}K{\ displaystyle K}
• Vuonna 2019 julkaistut Harvey- ja van der Hoeven -algoritmit: monimutkaisuus , mutta käytännössä hyödytön.O(eiHirsi⁡ei){\ displaystyle {\ mathcal {O}} (n \ log n)}

Viimeisimmät prosessorit toteuttavat kertomisen elektronisten piirien muodossa, mutta käsittelevät vain rajoitetun kokoisia kokonaislukuja. Tällaisia ​​piirejä kutsutaan kertojiksi .

Muut kertolaskut

• Matriisien kertolasku

Huomautuksia ja viitteitä

1. (en) David Harvey ja Joris Van Der Hoeven, ”  Kokonaisluvun kertolasku ajassa O (n log n)  ” , HAL ,18. maaliskuuta 2019( lue verkossa ).
2. Céline Deluzarche, "  Unohda kertotaulukot: tässä on uusi ja paljon tehokkaampi menetelmä  " , Futura Sciences ,12. huhtikuuta 2019.
3. A. Karatsuba ja Yu. Ofman, ”  Monien digitaalisten numeroiden kertominen automaattisilla tietokoneilla  ” , Neuvostoliiton tiedeakatemian julkaisut , voi.  145,1962, s.  293–294
4. Kheira Bettayeb, "  La multiplication reinventé  " , CNRS: ssä ,15. toukokuuta 2019(käytetty 26. kesäkuuta 2019 ) .

Katso myös

• Yhdeksän todiste
• Henkinen laskutoimitus

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">