Jakoalgoritmi

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

Jakolalgoritmi on algoritmi , joka laskee kahdelle annetulle kokonaisluvulle ja niiden osamäärän ja/tai jäännöksen jaon tuloksen jäännöksellä . Osa algoritmeista on suunniteltu manuaalisiin laskelmiin, osa on toteutettu digitaalisissa piireissä ja ohjelmistoissa. $N$ $D$

Jakoalgoritmit jaetaan kahteen laajaan luokkaan: hidas jako ja nopea jako. Hidas jako-algoritmit tuottavat yhden luvun tuloksesta iteraatiota kohden. Esimerkkejä hitaasta jaosta ovat jakoalgoritmit , joissa on palautus , ei palautusta ja SRT . Nopeat jakomenetelmät alkavat approksimoimalla lopullinen osamäärä ja tuottavat kaksi kertaa niin monta numeroa lopullisessa tuloksessa jokaisella iteraatiolla. Newton-Rapson- ja Goldschmidt - algoritmit kuuluvat tähän luokkaan.

Näiden algoritmien muunnelmat mahdollistavat nopeiden kertolaskualgoritmien käytön . Tämän seurauksena suurilla kokonaisluvuilla jakolaskuon tarvittava laskenta-aika on sama (vakiokertoimeen asti) kuin kertolaskussa tarvittava aika, riippumatta siitä, kumpaa listatuista algoritmeista ei käytetä.

Keskustelussa käytetään merkintää missä $N/D=(Q,R)$

$N$ - osoittaja (osinko)
$D$ - nimittäjä (jakaja)

ovat syötetyt numerot ja

$K$ - yksityinen
$R$ - loput

ovat tuotos.

Jakaminen vähennyksellä

Yksinkertaisin algoritmi, joka on historiallisesti rakennettu suurimpaan yhteisen jakaja - algoritmiin ja joka on esitetty Euclidin Principiassa , kirjan VII lauseessa 1, löytää kahden positiivisen kokonaisluvun jaon loppuosan käyttämällä vain vähennyslaskua ja vertailua:

R : = N , kun taas R >= D do R : = R − D - pään palautus R

Todiste siitä, että osamäärä ja jäännös ovat olemassa ja ovat ainutlaatuisia (kuvattu artikkelissa Jako jäännösjäännöksellä ), antaa täydellisen jakoalgoritmin, joka perustuu yhteen-, vähennyksiin ja vertailuihin:

funktio jako ( N , D ) jos D = 0 niin virhe ( DivisionByZero ) loppu jos D < 0 niin ( Q , R ) : = jako ( N , − D ); palauttaa ( − Q , R ) lopeta jos N < 0 sitten ( Q , R ) : = jakaa ( − N , D ) jos R = 0 niin palauttaa ( − Q , 0 ) muuten palauttaa ( − Q − 1 , D − R ) ) loppu loppu -- Tässä N >= 0 ja D >= 0 palauttaa jako_allekirjoittamaton ( N , D ) loppu funktio divide_signed ( N , D ) Q : = 0 ; R : = N kun taas R >= D do Q : = Q + 1 R : = R − D loppu paluu ( Q , R ) loppu

Tämä menettely antaa aina . Koska algoritmi on hyvin yksinkertainen, se vaatii vaiheita ja on siksi eksponentiaalisesti hitaampi kuin algoritmit, kuten pitkäjako. Algoritmi on hyödyllinen, jos (askeleita) tiedetään olevan vähän (riippuen lähtömäärästä). $R\geqslant 0$ $\Omega (Q)$ $K$

Sarakejako

Pitkä jako on tavallinen moninumeroinen desimaalilukualgoritmi, jota käytetään jakamiseen kynällä ja paperilla. Se siirtyy asteittain vasemmalta oikealle osingosta vähentäen jakajan suurimman mahdollisen kerrannaisen kussakin vaiheessa. Kertoimesta tulee osamäärä, ja lopullisesta erotuksesta tulee jaon jäännös.

Kun algoritmia käytetään kannassa 2, tämä menetelmä muodostaa perustan luonnollisten lukujen jakamiselle jäännöksellä. Lyhyt jako on muunnelma pitkästä jaosta, joka sopii jakamiseen yhdellä numerolla. Vähennysalgoritmi , joka tunnetaan myös murtoosamäärämenetelmänä , on vähemmän tehokas jako sarakkeella, mutta on helpompi ymmärtää. Kun sallitaan suuremman kerrannaisen vähentäminen kuin jokaisessa vaiheessa, antaa enemmän vapautta luoda muunnelmia pitkästä jaosta.

Kokonaislukujen jako (merkitsemätön) jäännöksellä

Yllä oleva algoritmi, binääriversio tunnetusta jaosta pituusasteiksi , jakaa luvulla asettamalla osamäärän sisään ja lopun sisään . Kaikki arvot käsitellään etumerkittöminä kokonaislukuina. $N$ $D$ $K$ $R$

jos D = 0 niin virhe ( DivisionByZeroException ) loppu -- Jako nollalla Q : = 0 -- Osamäärän ja jäännöksen alkuarvot ovat 0 R : = 0 i : = n − 1 .. 0 do -- Tässä n on numerobitti NR:ssä : = R << 1 - R:n siirto vasemmalle 1 bitillä R ( 0 ) : = N ( i ) - Aseta R:n vähiten merkitsevä bitti yhtä suureksi kuin jaon bitti i. jos R > = D niin R : = R − D Q ( i ) : = 1 loppupää Esimerkki

Ota ( ) ja ( ) $N=1100_{2}$ ${\displaystyle 12_{10))$ $D=100_{2}$ $4_{10}$

Vaihe 1 : Aseta R = 0 ja Q = 0
Vaihe 2 : Ota i = 3 (yksi vähemmän kuin N:n bittien määrä)
Vaihe 3 : R = 00 (siirrä vasemmalle 1)
Vaihe 4 : R = 01 (laita R (0 ) yhtä suuri kuin N(i))
Vaihe 5 : R < D, joten ohita komento

Vaihe 2 : Aseta i = 2
Vaihe 3 : R = 010
Vaihe 4 : R = 011
Vaihe 5 : R < D, ohita komento

Vaihe 2 : Aseta i = 1
Vaihe 3 : R = 0110
Vaihe 4 : R = 0110
Vaihe 5 : R >= D, komento suoritetaan
Vaihe 5b : R = 10 (R−D)
Vaihe 5c : Q = 10 (asetettu Q(i) yhtä kuin 1)

Vaihe 2 : Aseta i = 0
Vaihe 3 : R = 100
Vaihe 4 : R = 100
Vaihe 5 : R >= D, komento suoritetaan
Vaihe 5b : R = 0 (R−D)
Vaihe 5c : Q = 11 (asetettu Q(i) yhtä kuin 1)

Lopeta ( ) ja .
$Q=11_{2}$ ${\displaystyle 3_{10))$ $R = 0$

Hitaat jakomenetelmät

Kaikki hidas jakomenetelmät perustuvat standardiin toistuvuusrelaatioon [1]

R_{j+1}=B\kertaa R_{j}-q_{n-(j+1)}\kertaa D,

missä:

${\displaystyle R_{j))$ on jaon j:s osajäännös
B on luvun kanta (yleensä yhtä kuin 2 tietokoneissa ja laskimissa)
${\displaystyle q_{n-(j+1)))$ on osamäärä paikassa , jossa numeroiden paikat numeroidaan vähemmän merkitsevistä numeroista (0) suurempiin numeroihin ( ) $n-(j+1)$ $n-1$
$n$ − yksityisten merkkien määrä
$D$ − jakaja

Palautetaan divisioona

Rekonstruktiivinen jako toimii liukulukujen murtoluvuilla ja riippuu oletuksesta . $0<D<N$

Yksityiset numerot muodostetaan joukosta . $q$ $\{0,1\}$

Peruspalautusalgoritmi binäärille (kanta 2):

R : = N D : = D << n -- R:n ja D:n on oltava kaksi kertaa pidempiä sanoja kuin N ja Q i : lle : = n − 1 .. 0 do -- Esimerkiksi 31..0 32-bittiselle R :lle : = 2 * R − D -- Koevähennys siirretystä arvosta (kahdella kertominen on binääritulkinnan muutos), jos R >= 0 sitten q ( i ) : = 1 -- Tulos on bitti 1 muuten q ( i ) : = 0 -- Tulos on bitti 0 R : = R + D -- Uusi osajäännös on yhtä suuri kuin (palautettu) siirretyn arvon loppupää -- Tässä: N = osinko, D = jakaja, n = bittien määrä, R = osajäännös, q(i) = osamäärän bitti #i

Algoritmin variantti, joka ei toteuta erikseen , säilyttää sen, eikä sitä siksi tarvitse lisätä takaisin tapauksessa . $2R$ $D$ $R<0$

Ei-palauttava jako

Ei-palauttava jako käyttää joukkoa numeroita osamäärän numeroina sijasta . Algoritmi on monimutkaisempi, mutta sen etuna on chipeissä toteutettuna, että osamääräbittiä kohden on vain yksi päätös ja yksi yhteen-/vähennys. Vähennyksen jälkeen ei ole palautusvaihetta, mikä voi vähentää operaatioiden määrää puoleen ja antaa algoritmin toimia nopeammin [2] . Ei-palauttava jakoalgoritmi binäärisille (kanta 2) positiivisille luvuille: ${\näyttötyyli \{-1,1\))$ $\{0,1\}$

R : = N D : = D << n -- R:n ja D:n on oltava kaksi kertaa pidempiä sanoja kuin N ja Q , jos i = n − 1 .. 0 do -- Esimerkiksi 31..0 32 bitille, jos R > = 0 sitten q [ i ] : = + 1 R : = 2 * R − D else q [ i ] : = − 1 R : = 2 * R + D loppu , jos loppu -- Tässä: N = osinko, D = jakaja, n = bittien määrä, R = osajäännös, q(i) = osamäärän bitti #i.

Jos noudatamme tätä algoritmia, saamme osamäärän epästandardissa muodossa, joka koostuu luvuista -1 ja +1. Tämä lomake on muutettava binäärimuotoon. Esimerkki:

Osamäärän muuntaminen numeroiksi : $\{0,1\}$
Alkaa:	$Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}$
1. Muodostamme positiivisen termin:	$P=11101010\,$
2. Muodostamme negatiivisen termin:	$M=00010101\,$
3. Vähennä: : $PM$	$Q=11010101\,$
Negatiivinen termi esitetään binäärisenä käänteisenä , ei kahden komplementtina

Jos −1-merkit tallennetaan nolliksi (0), kuten tavallisessa esityksessä, laskenta on triviaali : se suorittaa bittikohtaisen komplementin (bitti korvataan bitin komplementilla) alkuperäisestä . $K$ $P$ $K$ $M$ $K$

Q : = Q − bitti . bnot ( Q ) -- Jos Q:n −1 numerot esitetään nollina.

Lopuksi tällä algoritmilla lasketut osamäärät ovat aina parittomat ja jäännös R on sisällä . Esimerkiksi . Jotta se saadaan positiiviseen loppuosaan, otamme yhden palautusvaiheen sen jälkeen, kun se on pienennetty epätyypillisestä lomakkeesta vakiomuotoon: $-D\leqslant R\leqslant D$ $5/2=3R-1$ $K$

jos R < 0 niin Q : = Q − 1 R : = R + D loppu jos

Todellinen loppuosa on R >> n. Kuten palautuksen yhteydessä, vähiten merkitseviä bittejä käytetään samassa järjestyksessä kuin osamääräbitit muodostetaan , ja on järkevää käyttää yhtä rekisterisiirtoa molemmille numeroille samanaikaisesti. $R$ $K$

SRT:n osasto

Jako on nimetty tekijöiden nimien ensimmäisten kirjainten mukaan (Sweeney, Robertson, Tocher). SRT-jako on suosittu jakomenetelmä monissa mikroprosessoreissa [3] [4] . Jakaminen on samanlainen kuin jakaminen ilman palautusta, mutta se käyttää osinkoon ja jakajaan perustuvaa hakutaulukkoa osamäärän määrittämiseen.

Merkittävin ero on, että yksityiselle käytetään redundanttia esitystä . Jos esimerkiksi SRT:n 4 kantajako on toteutettu, jokainen osamäärä valitaan viidestä mahdollisuudesta : . Tämän vuoksi osamäärän numeron valinnan ei tarvitse olla tarkka. Myöhemmin osamäärälukuja voidaan korjata. Esimerkiksi numeroparit ja ovat vastaavia, koska . Tämän toleranssin avulla voit valita osamäärän numerot perustuen vain osingon ja jakajan merkittävimpiin muutamaan bittiin sen sijaan, että vähentäisit koko pituutta. Tämä yksinkertaistaminen puolestaan mahdollistaa kantaluvun käytön luvuille, jotka ovat suurempia kuin 2. ${\näyttötyyli \{-2,-1,0,+1,+2\))$ ${\näyttötyyli {0,+2}}$ ${\näyttötyyli {1,-2}}$ $0{\times }4+2=1{\times }4-2$

Kuten ei-palauttavassa jaossa, viimeiset vaiheet ovat lukujen vähentäminen koko pituudelta, jotta saadaan osamäärän viimeinen bitti, ja osamäärän muuntaminen vakiobinääriksi.

Intel Pentium -suorittimien pahamaineinen kelluva jakovirhe johtui koodatusta hakutaulukosta. Viisi taulukon 1066 solusta jätettiin virheellisesti pois [5] [6] .

Nopeat jakomenetelmät

Newton–Rapson-divisioona

Newton–Rapson-jako käyttää Newtonin menetelmää luvun käänteisluvun selvittämiseen ja kertoo sen käänteisluvulla saadakseen tuloksena olevan osamäärän . $D$ $N$ $K$

Newton-Rapson-jaon vaiheet:

Laskemme jakajan käänteisarvion . $X_{0}$ $1/D$ $D$
Laskemme peräkkäin tarkempia approksimaatioita käänteisarvosta. Tämä on paikka, jossa itse asiassa käytetään Newton-Rapson-menetelmää. ${\displaystyle X_{1},X_{2},\ldots ,X_{S))$
Laskemme osamäärän kertomalla osingon jakajan käänteisluvulla: . $Q=NX_{S}$

Jotta voit käyttää Newtonin menetelmää luvun käänteisluvun löytämiseen , sinun on löydettävä funktio , jonka pisteessä on nolla . Ilmeisesti tämä funktio on , mutta Newton-Rapson-iteraatiot eivät ole onnistuneet sille, koska niitä ei voida suorittaa tietämättä luvun käänteislukua (lisäksi menetelmä yrittää laskea tarkan käänteisluvun yhdessä vaiheessa, eikä tee iteratiivisia parannuksia ). Toimiva funktio on se , jolle Newton-Rapson-iteraatio antaa $D$ $f(X)$ $X=1/D$ $f(X)=DX-1$ $D$ $f(X)=(1/X)-D$

X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \ yli -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),

joka voidaan laskea käyttämällä vain kerto- ja vähennyslaskua tai kahta kerto- ja yhteenlaskua . $X_{i}$

Laskennallisesta näkökulmasta lausekkeet ja eivät ole vastaavia. Saadaksesi 2n bitin tarkkuuden käyttämällä toista lauseketta, sinun on laskettava tulo väliltä ja kaksinkertaisella tarkkuudella määritettyyn tarkkuuteen ( n bittiä). Tulo sitä vastoin tarvitsee laskea vain n bitin tarkkuudella, koska ensimmäiset n bittiä (binääripisteen jälkeen) ovat nolla. $X_{i+1}=X_{i}+X_{i}(1-DX_{i})$ $X_{i+1}=X_{i}(2-DX_{i})$ $X_{i}$ $(2-DX_{i})$ $X_{i}$ $X_{i}$ $(1-DX_{i})$ $(1-DX_{i})$

Jos virhe on määritelty , niin ${\displaystyle \varepsilon _{i}=1-DX_{i))$

{\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\ &=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i)) ^{2}.\\\end{tasattu}}

Tämä neliövirhe kussakin iteraatiovaiheessa (niin sanottu Newton-Rapson-menetelmän neliöllinen konvergenssi ) saa aikaan sen, että tuloksen oikeiden numeroiden määrä noin kaksinkertaistuu jokaisessa iteraatiossa , ominaisuus, joka tulee erittäin tärkeäksi, kun havaitut luvut ovat monta numeroa.. Mutta se tarkoittaa myös sitä, että menetelmän alkuperäinen konvergenssi voi olla suhteellisen hidasta, varsinkin jos arvo on huonosti valittu. $X_{0}$

Alkuarvion valinnan aliongelmassa on kätevää käyttää jakajan siirtoa siten, että se on välillä , samalla kun sovelletaan samaa siirtoa osinkoon , jotta osamäärä ei muutu. Sitten voidaan käyttää lomakkeessa olevaa lineaarista approksimaatiota $X_{0}$ $D$ $0{,}5\leqslant D\leqslant 1$ $N$

X_{0}=T_{1}+T_{2}D\noin {\frac {1}{D}}\,

Newton-Rapson-menetelmän alustamiseksi. Tämän likiarvon maksimi absoluuttisen virheen minimoimiseksi välissä tulisi käyttää $[0{,}5,1]$

X_{0}={48 \over 17}-{32 \over 17}D.\,

Lineaariset approksimaatiokertoimet määritellään seuraavasti. Virheen itseisarvo on . Virheen maksimiabsoluuttisen arvon minimi määritetään Tšebyševin ekvivalenttivärähtelylauseen mukaan , jota sovelletaan . Paikallinen funktion minimi on kohdassa, jossa , jolla on ratkaisu . Tämän minimin funktiolla tulisi olla arvo, jolla on vastakkainen etumerkki suhteessa välin ääripisteisiin, nimittäin . Kaksi yhtälöä kahdessa tuntemattomassa antavat ainutlaatuisen ratkaisun ja , ja suurin virhe on . Tätä approksimaatiota käytettäessä alkuarvon virheen itseisarvo on pienempi kuin $|\varepsilon _{0}|=|1-D(T_{1}+T_{2}D)|$ $F(D)=1-D(T_{1}+T_{2}D)$ $F(D)$ $F'(D)=0$ $D=-T_{1}/(2T_{2})$ $F(1/2)=F(1)=-F(-T_{1}/(2T_{2}))$ $T_{1}=48/17$ $T_{2}=-32/17$ $F(1)=1/17$

\vert \varepsilon _{0}\vert \leqslant {1 \over 17}\noin 0{,}059.\,

On mahdollista muodostaa polynomi, jonka aste on suurempi kuin 1, laskemalla kertoimet Remez-algoritmin mukaan . Tällöin alkuperäinen approksimaatio vaatii enemmän laskentaa, joka voidaan kompensoida pienemmällä määrällä Newton–Rapson-iteraatioita.

Koska tämän menetelmän konvergenssi on täsmälleen neliöllinen, se on riittävä

S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,

vaiheet arvon laskemiseksi binääripaikkoihin asti. Tämä vastaa 3:a IEEE:n kaksinpelissä ja 4 nelinpelissä ja pidennetyssä nelinpelissä . $P\,$

Pseudokoodi

Seuraava pseudokoodi laskee N :n ja D : n osamäärän P binäärinumeroon asti:

Ilmaise D missä (vakioliukulukuesitys) // heitetään arvoon 0,5 ja 1, mikä voidaan tehdä bittisiirrolla / vähentämällä eksponentti // ennalta lasketut vakiot samalla tarkkuudella kuin D- toistoajat // voidaan laskea ennakkoon kiinteään P- päätypalautukseen

{\displaystyle M\times 2^{e))

1\leqslant M<2

D^{\prime }{\colon }=D/2^{e+1}

N^{\prime }{\colon }=N/2*{e+1}

X{\colon }=48/17-32/17\times D^{\prime }

\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,

X{\colon }=X+X\times (1-D^{\prime }\times X)

N^{\prime }\times X

Esimerkiksi kaksinkertaisessa tarkkuudessa liukulukujaossa tämä menetelmä käyttää 10 kertolaskua, 9 yhteenlaskua ja 2 siirtoa.

Newton–Rapson-divisioonan muunnelmia

Newton-Rapson-jakomenetelmää voidaan muokata hieman nopeammaksi. Kun N ja D on siirretty siten, että D on välillä [0.5, 1.0], alustetaan

X:={\frac {140}{33}}+D\cdot \left({\frac {-64}{11}}+D\cdot {\frac {256}{99}}\right )

Tämä on paras neliöllinen approksimaatio ja antaa absoluuttisen virhearvon enintään . Parametrit valitaan siten, että valitaan virhe, joka on yhtä suuri kuin ensimmäisen tyypin Chebyshev-polynomin kolmannen kertaluvun arvo . Kertoimet on laskettava etukäteen ja koodattava menetelmään. ${\frac {1}{D}}$ $1/99$

Sitten silmukassa käytämme iteraatiota, joka nostaa virheen kuutioksi.

E:=1-D\cdot X

Y:=X\cdot E

X:=X+Y+Y\cdot E

Jos silmukka suoritetaan, kunnes se lähestyy johtavaa bittiä, iteraatioiden määrä on enintään $X$ $1/D$ $P$

\left\lceil \log _{3}\left({\frac {P+1}{\log _{2}99}}\right)\right\rceil

joka on yhtä monta kertaa 99 kuutiota saada . Sitten $2^{P+1}$

Q:=N\cdot X

on yhtä suuri kuin osamäärä biteihin asti . $P$

Korkeamman asteen polynomien käyttäminen alustuksissa tai iteraatioissa johtaa suorituskykyongelmiin, koska ylimääräisiä kertolaskuja olisi parempi käyttää lisäämään iteraatioita.

Goldschmidtin osasto

Goldschmidtin jako [7] (Robert Elliott Goldschmidt) käyttää iteratiivista prosessia, jossa osinko ja jakaja kerrotaan toistuvasti samalla kertoimella , joka valitaan siten, että jakaja konvergoi 1:een. Tämä saa osingon konvergoimaan osamäärään : $F_{i}$ $K$

Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}

Goldschmidtin jaon vaiheet:

Luomme kertoimelle likiarvon . $F_{i}$
Kerro osinko ja jakaja . $F_{i}$
Jos jakaja on tarpeeksi lähellä yhtä, palauta osinko, muussa tapauksessa palaa vaiheeseen 1.

Oletetaan , että se on skaalattu arvoon , joista jokainen perustuu : $N/D$ $0<D<1$ $F_{i}$ $D$

F_{i+1}=2-D_{i}.

Kerrotaan osinko ja jakaja kertoimella ja saadaan:

{\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1} }{F_{i+1}}}.

Riittävän määrän iteraatioita jälkeen . $k$ ${\displaystyle Q=N_{k))$

Goldschmidt-menetelmää käytetään AMD Athlon -prosessoreissa ja myöhemmin [8] [9] . Se tunnetaan myös nimellä Anderson Earle Goldschmidt Powers (AEGP) -algoritmi, ja se on toteutettu useissa IBM-prosessoreissa [10] [11] . Vaikka menetelmän konvergenssi on sama kuin Newton–Rapmon-toteutuksessa, yksi Goldschmidt-menetelmän eduista on, että kertoimet osoittajassa ja nimittäjässä voidaan tehdä rinnakkain [11] .

Binomiaalilause

Goldschmidtin menetelmää voidaan käyttää tekijöiden kanssa, jotka mahdollistavat yksinkertaistamisen Newtonin binomiaalilla . Oletetaan, että N/D kerrotaan potenssilla kaksi niin, että . Valitsemme ja . Tämä antaa $D\in ({\tfrac {1}{2)),1]$ $D=1-x$ $F_{i}=1+x^{2^{i))$

{\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+ x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1 +x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\noin 1} }

Vaiheiden jälkeen nimittäjä voidaan pyöristää ylöspäin suhteellisella virheellä $n$ $(x\in [0,{\tfrac {1}{2))))$ ${\näyttötyyli 1-x^{2^{n))}$ $yksi$

\varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}

jonka suurin arvo on , mikä tarjoaa binäärinumeroiden vähimmäistarkkuuden . ${\näyttötyyli 2^{-2^{n))}$ $x={1 \over 2}$ $2^{n}$

Menetelmät suurille numeroille

Laitteistossa toteutettaviksi tarkoitetut menetelmät eivät tyypillisesti laske kokonaislukuja, joissa on tuhansia tai miljoonia desimaalilukuja, mikä on yleistä esimerkiksi kryptografian modulo - laskelmissa . Näille suurille lukuille tehokkaammat algoritmit muuntaa ongelman pieneen kertolaskumäärään, mikä voidaan tehdä asymptoottisesti tehokkailla kertolaskualgoritmeilla , kuten Karatsuban algoritmilla , Tum-Cookin kertolaskulla tai Schönhage-Strassenin algoritmilla . Tämän seurauksena jaon laskennallinen monimutkaisuus on samaa luokkaa (vakiolla kertomiseen asti) kuin kertolasku. Esimerkkejä ovat yllä kuvattu pelkistys Newtonin kertolaskuksi [12] sekä hieman nopeampi Bournickel-Ziegler-jako [13] , Baret ja Montgomeryn [14] algoritmit . Etenkin Newtonin menetelmä on tehokas skenaarioissa, joissa täytyy tehdä useita jakoja tietyllä luvulla, koska käänteisluvun alun löytämisen jälkeen kutakin kertolaskua varten tarvitaan vain yksi (pelkistetty) kertolasku.

Jako vakiolla

Jakaminen vakiolla vastaa kertomista sen käänteisarvolla . Koska nimittäjä on vakio, myös käänteisluku on vakio . Sitten voit laskea arvon kerran ja laskelmien aikana teemme kertolaskua jakolaskua . Liukulukuaritmetiikassa käyttö aiheuttaa pienen ongelman liittyen koodin optimointiin [a]-kääntäjien toimesta , mutta kokonaislukuaritmetiikassa jäännös on aina nolla, mikäli . $D$ ${\frac {1}{D}}$ $1/D$ $N\times {\frac {1}{D))$ $N/D$ ${\frac {1}{D}}$ $|D|>1$

Ei tarvitse käyttää täsmälleen , voit käyttää mitä tahansa arvoa , joka pienenee arvoon . Esimerkiksi, kun jaat kolmella, voit käyttää murtolukuja , tai . Siksi, kun potenssi on kaksi, jakoaskel voidaan vähentää nopeaksi siirroksi oikealle. Vaikutuksena laskeminen kuinka korvaa jakamisen kerto- ja siirrolla. Huomaa, että juuri tämä menettely on olennainen tässä, koska se johtaa nollaan. $1/D$ $X/Y$ $1/D$ $1/3$ $2/6$ $3/9$ $194/582$ $Y$ $N/D$ ${\frac {N\times X}{Y))$ $N\times {\frac {X}{Y))$

Kuitenkin, jos on jo kahden potenssi, ei ole olemassa ja jotka täyttävät yllä olevat ehdot. Onneksi antaa kokonaislukuaritmetiikassa täsmälleen saman tuloksen kuin , vaikka ei olekaan täsmälleen yhtä suuri kuin , mutta "riittävän lähellä", joten approksimoinnin aiheuttama virhe on bitteissä, jotka poistuvat siirtotoiminnon jälkeen [15] [ 16 ] [17] [b] $D$ $X$ $Y$ ${\frac {N\times X}{Y))$ $N/D$ $X/Y$ $1/D$

Erityisenä esimerkkinä kiinteän pisteen aritmetiikasta 32-bittisten etumerkittömien kokonaislukujen tapauksessa jako kolmella voidaan korvata kertomalla luvulla , eli kertomalla luvulla 2863311531 ( heksadesimaali 0xAAAAAAAB), jota seuraa 33 bitin siirto oikealle. Arvo 2863311531 lasketaan muodossa ja pyöristetään ylöspäin. Vastaavasti jako 10:llä voidaan ilmaista kertomalla luvulla 3435973837 (0xCCCCCCD), jota seuraa jako (tai 35 bitin siirto oikealle) [19] . OEIS antaa vakiojonon kertolaskua varten muodossa A346495 ja oikealle siirrolle muodossa A346496 . ${\displaystyle {\tfrac {2863311531}{2^{33))))$ ${\tfrac {2^{33}}{3}}$ $2^{{35}}$

Yhteiselle -bittiselle etumerkittömälle kokonaislukujaolle, jossa jakaja ei ole kahden potenssi, seuraava identiteetti muuntaa jaon kahdeksi -bittiseksi yhteen-/vähennyslaskuksi, yhdeksi kertolaskuksi -bitti bittiluvuilla (jossa vain tuloksen korkea puoli käytetään), ja useita työvuoroja, esilaskentaa ja : $x$ $D$ $x$ $x$ $x$ $k=x+\lceil \log _{2}{D}\rceil$ $a=\left\lceil {\tfrac {2^{k}}{D}}\right\rceil -2^{x}$

$\left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {Nb}{2}}\right\rfloor +b }{2^{kx-1}}}\oikea\rfloor$ missä $b=\left\lfloor {\frac {Na}{2^{x))}\right\rfloor$

Joissakin tapauksissa jako vakiolla voidaan tehdä jopa lyhyemmässä ajassa korvaamalla "vakiolla kertominen" sarjalla siirtymiä ja yhteen- tai vähennyslaskuja [20] . Erityisen kiinnostava on jako 10:llä, jonka tarkka osamäärä saadaan tarvittaessa jäännöksellä [21] .

Katso myös

Muistiinpanot

↑ Huolimatta siitä, kuinka "pieni" ongelma on optimoinnin aiheuttama, tämä optimointi on yleensä piilotettu "quick math" -lipun taakse nykyaikaisissa kääntäjissä .
↑ Nykyaikaiset kääntäjät käyttävät tyypillisesti tätä kokonaislukujen kerto- ja muutosoptimointia. Vain ajon aikana tunnetuille vakioille ohjelman on toteutettava itse optimointi [18]

↑ Morris, Iniewski, 2017 .
↑ Flynn Stanford EE486 (Advanced Computer Aithmetic Division) - Luku 5 Moniste (Division) . Stanfordin yliopisto . Haettu 10. tammikuuta 2022. Arkistoitu alkuperäisestä 18. huhtikuuta 2022. (määrätön)
↑ Harris, Oberman, Horowitz, 1998 .
↑ McCann, Pippenger, 2005 , s. 1279–1301.
↑ Liukulukuvirheen tilastollinen analyysi . Intel Corporation (1994). Haettu 22. lokakuuta 2013. Arkistoitu alkuperäisestä 23. lokakuuta 2013. (määrätön)
↑ Oberman, Flynn, 1995 .
↑ Goldschmidt, 1964 .
↑ Oberman, 1999 , s. 106-115.
↑ Soderquist, Leeser, 1997 , s. 56-66.
↑ Anderson, Earle, Goldschmidt, Powers, 1997 .
↑ 1 2 Guy, Peter, Ferguson, 2005 , s. 118-139.
↑ Hasselström, 2003 .
↑ Burnikel, Ziegler, 1998 .
↑ Barrett, 1987 , s. 311-323.
↑ Granlund, Montgomery, 1994 , s. 61–72.
↑ Möller, Granlund, 2011 , s. 165-175.
↑ naurettava_kala. "Labor of Division (Episode III): Faster Unsigned Division by Constants" Arkistoitu 8. tammikuuta 2022 Wayback Machinessa . 2011.
↑ ridiculous_fish libdivide, optimoitu kokonaislukujako . Haettu 6. heinäkuuta 2021. Arkistoitu alkuperäisestä 23. marraskuuta 2021. (määrätön)
↑ Warren Jr., 2013 , s. 230-234.
↑ LaBudde, Robert A.; Golovchenko, Nikolai; Newton, James; Parker, David; Massmind: Binary Division by a Constant Arkistoitu 9. tammikuuta 2022 Wayback Machinessa
↑ Vokaalit, 1992 , s. 81–85.

Kirjallisuus

RA vokaalit. Jako numerolla 10 // Australian Computer Journal. - 1992. - T. 24 , no. 3 .
James E. Morris, Krzysztof Iniewski. Nanoelektronisten laitesovellusten käsikirja . - CRC Press, 2017. - ISBN 978-1-351-83197-0 .
David L. Harris, Stuart F. Oberman, Mark A. Horowitz. SRT-osasto: Arkkitehtuurit, mallit ja toteutukset . - Stanfordin yliopisto, 1998.
Mark McCann, Nicholas Pippenger. SRT Division Algorithms as Dynamical Systems // SIAM Journal on Computing. - 2005. - T. 34 , no. 6 . - doi : 10.1137/S009753970444106X .
Stuart F. Oberman, Michael J. Flynn. Jakoalgoritmien ja toteutusten analyysi . – Stanfordin yliopisto, 1995.
Robert E. Goldschmidt. Lähentymisperusteisen jaon sovellukset . - MIT, 1964. - (M.Sc. väitöskirja).
Stuart F. Oberman. Liukulukujako- ja neliöjuurialgoritmit ja toteutus AMD-K7-mikroprosessorissa // Proceedings of the IEEE Symposium on Computer Aithmetic. - 1999. - S. 106-115 . - doi : 10.1109/ARITH.1999.762835 .
Peter Soderquist, Miriam Leeser. Jako ja neliöjuuri: oikean toteutuksen valitseminen // IEEE Micro. - 1997. - heinä-elokuu ( nide 17 , numero 4 ). - doi : 10.1109/40.612224 .
SF Anderson, JG Earle, RE Goldschmidt, DM Powers. IBM 360/370 -malli 91: liukulukujen suoritusyksikkö // IBM Journal of Research and Development . - 1997. - tammikuuta.
Jopa Guy, Siedel Peter, Warren Ferguson. Goldschmidtin jakoalgoritmin parametrinen virheanalyysi // Journal of Computer and System Sciences. - 2005. - Helmikuu ( nide 70 , numero 1 ). - doi : 10.1016/j.jcss.2004.08.004 .
Karl Hasselström. Suurten kokonaislukujen nopea jako: Algoritmien vertailu . - Royal Institute of Technology, 2003. - ((tutkielma) M.Sc. in Computer Science).
Christoph Burnickel, Joachim Ziegler. Nopea rekursiivinen osasto . - Max-Planck-Institut für Informatik, 1998.
Paul Barrett. Rivest Shamirin ja Adlemanin julkisen avaimen salausalgoritmin toteuttaminen tavallisessa digitaalisessa signaaliprosessorissa // Proceedings on Advances in cryptology---CRYPTO '86 . — Lontoo, UK: Springer-Verlag, 1987. — s. 311–323. — ISBN 0-387-18047-8 .
Torbjörn Granlund, Peter L. Montgomery. Jako muuttumattomilla kokonaisluvuilla kertolaskulla // SIGPLAN-ilmoitukset. - 1994. - Kesäkuu ( nide 29 , numero 6 ). - doi : 10.1145/773473.178249 .
Niels Möller, Torbjörn Granlund. Parannettu jako muuttumattomilla kokonaisluvuilla // IEEE Transactions on Computers. - 2011. - Helmikuu ( nide 60 , numero 2 ). - doi : 10.1109/TC.2010.143 .
Henry S. Warren Jr. Hakkerin ilo . - 2. - Addison Wesley - Pearson Education, Inc. , 2013. - ISBN 978-0-321-84268-8 .

Lue lisää lukemista varten

John JG Savard. Kehittyneet aritmeettiset tekniikat . quadribloc (2018). Haettu 16. heinäkuuta 2018. Arkistoitu alkuperäisestä 3. heinäkuuta 2018. (määrätön)

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