Pitkä aritmetiikka

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

Pitkät aritmeettiset - aritmeettiset operaatiot, jotka suoritetaan tietokoneella ( yhteen- , vähennys- , kerto- , jakolasku- , eksponentio- , alkeisfunktiot ) luvuille, joiden bittisyvyys ylittää tämän tietokoneen konesanan pituuden. Näitä toimintoja ei toteuteta laitteistolla, vaan ohjelmistolla käyttäen peruslaitteistoa pienempien tilausten kanssa työskentelyyn. Erikoistapaus - mielivaltainen tarkkuusaritmetiikka - viittaa aritmetiikkaan, jossa numeroiden pituutta rajoittaa vain käytettävissä olevan muistin määrä.

Sovellus

Pitkää aritmetiikkaa käytetään seuraavilla alueilla:

koodin kokoaminen pienen kapasiteetin prosessoreille ( mikro - ohjaimille ) . Esimerkiksi AVR - sarjan mikro-ohjaimissa on 10 - bittinen ADC ja 8-bittinen rekisteri . Tämä ei riitä käsittelemään tietoja ADC:stä; pitkä aritmetiikka on välttämätöntä;
kryptografia . Useimmat tiedon allekirjoitus- ja salausjärjestelmät käyttävät kokonaislukuaritmeettista modulo m:ää, jossa m on erittäin suuri luonnollinen luku, ei välttämättä alkulukua . Esimerkiksi RSA - salausmenetelmää , Rabinin salausjärjestelmää tai ElGamal -mallia toteutettaessa on varmistettava kertolasku- ja eksponentiotulosten tarkkuus luokkaa 10 309 ;
matemaattiset (katso ohjelmistoluettelo ) ja talousohjelmistot . Paperilla lasketun tuloksen tulee vastata tietokoneen tulosta viimeiseen numeroon. Erityisesti Windows-laskin ( Windows 95 :stä lähtien ) suorittaa neljä aritmeettista operaatiota paljon suuremmalla tarkkuudella kuin x86 -prosessori sallii . Tieteellisiin ja teknisiin laskelmiin käytetään harvoin pitkää aritmetiikkaa, koska syötetietojen virheet ovat yleensä paljon suurempia kuin pyöristysvirheet;
urheiluohjelmoinnin vakioaihe .

Tarvittava laitteisto toimiakseen pitkän aritmeettisen kanssa

Tarkkaan ottaen prosessorilta vaaditaan vain epäsuoraa osoitusta mielivaltaisen tarkkuuden aritmetiikkaan toteuttamiseksi ; kiinteän tarkkuuden aritmetiikassa pärjäät jopa ilman sitä. Tietyt prosessorin toiminnot kuitenkin nopeuttavat pitkää aritmetiikkaa ja yksinkertaistavat sen ohjelmointia.

Kanna lippua . Operaatiot "lisää/vähennä siirrolla", " Kierrä siirtobitin läpi ".
Epäsuora osoitus automaattisella lisäyksellä ja automaattisella vähennyksellä (indeksirekisteriä kasvatetaan tai pienennetään toimenpiteen jälkeen).
Kertominen w · w = 2 w ( sanasta sanaan kertominen, tulos on kaksoissana), jako 2 w / w = w (mahdollisella ylivuodolla ).

Toteutus ohjelmointikielillä

Ohjelmointikielissä on sisäänrakennetut tietotyypit, jotka eivät yleensä ylitä 64 bittiä (noin 10 19 ). Desimaalipitkä aritmetiikka toteutettiin Neuvostoliiton ohjelmointikielillä ALMIR - 65 MIR-1- tietokoneessa ja ANALYTIK MIR-2- tietokoneessa . Työskennelläksesi suurten numeroiden kanssa nykyaikaisissa ohjelmointikielissä on useita valmiita optimoituja kirjastoja pitkää aritmetiikkaa varten.

Useimmat toiminnalliset kielet antavat sinun vaihtaa tavallisesta aritmeettisesta pitkälle aritmeettiseen aritmetiikkaan ilman, että sinun tarvitsee muuttaa aritmeettista koodia. Esimerkiksi Erlang ja Scheme edustavat aina tarkkoja lukuja yhtä pitkiä. Standard ML :ssä kaikkien kokonaislukulajikkeiden toteutukset määritetään allekirjoituksen perusteella INTEGER, jolloin voit valita tarvittavan ulottuvuuden, mukaan lukien moduulin IntInf, joka toteuttaa mielivaltaisen tarkkuuden kokonaislukuja; PolyML-toteutus käyttää tätä moduulia oletuksena.

PascalABC.NET:ssä, Rubyssa , Pythonissa ja Javassa on sisäänrakennettuja kirjastoja suurten numeroiden käsittelyä varten .

Algoritmit

Kertolalgoritmit

Seuraavaa kokonaislukujen esitystä käytetään yleensä kuvaamaan algoritmeja. Pohja on valittu . Sitten pituus kokonaisluku voidaan esittää muodossa [1] : $\beta >1$ $n$

A=a_{n-1}\cdot \beta ^{n-1}+...+a_{1}\cdot \beta +a_{0},

missä $0\leq a_{i}\leq \beta -1.$

Perus

Se on koulun menetelmän mukainen algoritmi "sarakkeessa". Kestää aikaa missä ovat kerrottujen lukujen koot. $O(n\cdot m),$ $n,m$

Algoritmi voidaan esittää muodossa [1] [2] :

Algoritmi 1 BasecaseMultiply
Input: Output: for from to do $A=\summa \nolimits _{{i=0}}^{{m-1}}a_{i}\beta ^{i},B=\sum \nolimits _{{j=0}}^{{ n-1}}b_{j}\beta ^{j}$
$C=AB:=\summa \nlimits _{{k=0}}^{{m+n-1}}c_{k}\beta ^{k}$
$1:C\saa A\cdot b_{0}$
$2:$ $j$ $yksi$ $n-1$
$3:~~~~C\saa C+\beta ^{j}(A\cdot b_{j})$
$4:paluu~~C.$

Karatsuban kertominen

Karatsuban kertolaskumenetelmä kuuluu " hajoita ja hallitse " -paradigmaan. Algoritmin laskennallinen monimutkaisuus :

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

Tämä algoritmi on yksinkertainen toteutus [3] syöttötietojen jakamisesta, josta on tullut alla lueteltujen algoritmien perusta. Ajatuksena on jakaa yksi kertolaskuoperaatio lukuisille luvuille kolmeen kertolaskuoperaatioon luvuilla, joiden pituus on plus [1] . $n$ $n/2$ $Päällä)$

Kahden konesanaa suuremman luvun kertomiseksi Karatsuban algoritmia kutsutaan rekursiivisesti, kunnes luvut ovat tarpeeksi pieniä kertoakseen suoraan. Esimerkki tällaisesta algoritmista:

Algoritmi 2 KaratsubaMultiply
Input: Output: KaratsubaMultiply KaratsubaMultiply KaratsubaMultiply $A=\summa \nolimits _{{i=0}}^{{n-1}}a_{i}\beta ^{i},B=\sum \nolimits _{{j=0}}^{{ n-1}}b_{j}\beta ^{j}$
$C=AB:=\summa \nlimits _{{k=0}}^{{2n-1}}c_{k}\beta ^{k}$
$k\gets [n/2]$
$(A_{0},B_{0}):=(A,B)mod\beta ^{k},(A_{1},B_{1}):=(A,B)div\beta ^{k }$
$s_{A}\saa merkin(A_{0}-A_{1}),s_{B}\saa merkin(B_{0}-B_{1})$
$C_{0}\gets$ $(A_{0},B_{0})$
$C_{1}\gets$ $(A_{1},B_{1})$
$C_{2}\gets$ $(|A_{0}-A_{1}|,|B_{0}-B_{1}|)$
$return~C:=C_{0}+(C_{0}+C_{1}-s_{A}s_{B}C_{2})\beta ^{k}+C_{1}\beta ^{{ 2k}}$

Lasketaan : $x=12345\cdot 6789$

12345=12\cdot 1000+345

6789=6\cdot 1000+789

Kolme välikerrointa on laskettava:

C_{0}=345\cdot 789=272205

C_{1}=12\cpiste 6=72

C_{2}=C_{1}+C_{0}-(345-12)\cdot (789-6)=72+272205-333\cdot 783=11538

Tulos:

x=C_{1}\cpiste 1000^{2}+C_{2}\cpiste 1000+C_{0}

x=72\cdot 1000^{2}+11538\cdot 1000+272205=83810205

Tooman algoritmi

Tämä algoritmi on yleistys Karatsuba-algoritmista ja on nopeampi. Kun on annettu kaksi kokonaislukua ja , Toomin algoritmi jakaa ne pienempiin osiin, joista jokainen on yhtä pitkä kuin konesanan pituus, ja suorittaa operaatiot näille osille. Algoritmin laskennan monimutkaisuus: $A$ $B$ $k$ $O(n^{\ln(2k-1)/\ln(k)}).$

Tooma-3 algoritmi

Ajatuksen esitti ensimmäisen kerran A. L. Toom vuonna 1963 [4] , ja se koostuu syötetietojen (kertoimien) jakamisesta kolmeen yhtä suureen osaan (yksinkertaisuuden vuoksi kaikkia osia pidetään samanarvoisina). Toom-3 vähentää alkeiskertotoimintojen lukumäärää 9:stä 5:een. Algoritmin monimutkaisuus $O(n^{1.465}).$

Harkitse tätä algoritmia seuraavassa esimerkissä. Olkoon kaksi numeroa ja . Määritellään operaatioita numeroille, joiden koko on yhtä suuri kuin 1/3 alkuperäisten lukujen koosta (katso kuva). Oletetaan myös, että luvut vievät yhtä paljon muistia ja ovat jaollisia tarkalleen kolmella osalla, muuten täytämme molemmat luvut nollilla vaadittuun kokoon. $Y$ $X$

Sitten suoritetaan näiden osien kartoitus (parametrisointi) 2. asteen polynomeiksi.

X(t)=x_{2}\cpiste t^{2}+x_{1}\cpiste t+x_{0},

Y(t)=y_{2}\cpiste t^{2}+y_{1}\cpiste t+y_{0},

Otetaan käyttöön määritelmän mukaan sellainen, että polynomien arvot ovat vastaavasti yhtä suuria kuin syöteluvut ja . Numeroiden bittikohtaisessa esityksessä tämä luku on kaksi potenssiin, joka vastaa kunkin osan pituutta bitteinä. $b$ $X(b),~Y(b)$ $x$ $y$

Esittelemme myös polynomin:

W(t)=X(t)\cdot Y(t),

(yksi)

W(t)=w_{4}\cpiste t^{4}+w_{3}\cpiste t^{3}+w_{2}\cpiste t^{2}+w_{1}\cpiste t+w_ {0},

Kun alkiot on määritetty - polynomin kertoimet , niitä käytetään saadakseen , koska . Kertoimien koko on 2 kertaa suurempi (muistista) kuin osio tai . Lopullinen tuotetta vastaava luku löytyy lisäämällä siirrolla alla olevan kuvan mukaisesti. $w_{i}$ $W(t)$ $w=W(b)$ $x\cdot y=X(b)\cdot Y(b)=W(b)$ $w_{i}$ $x_{i}$ $y_{i}$ $x\cdot y$ $w_{i}$

Kertoimet voidaan laskea seuraavasti: ja niin edelleen, mutta tämä vaatii kaikki 9 kertolaskua: i:lle j=0,1,2, ja se vastaa yksinkertaista kertolaskua. $w_{i}$ $w_{4}=x_{2}\cdot y_{2},w_{3}=x_{2}\cdot y_{1}+x_{1}\cdot y_{2},~~w_{2}= x_{2}\cdot y_{0}+x_{1}\cdot y_{1}+x_{0}\cdot y_{2}$ $x_{i}\cdot y_{j}$

Sen sijaan otettiin erilainen lähestymistapa. lasketaan kohdassa (1) 5 pisteellä eri . ${\näyttötyyli X(t),Y(t)}$ $t$

Alla oleva taulukko näyttää polynomien arvot yhtälössä (1)

$t = 0$	$x_{0}\cdot y_{0}$	$W(0)~~~=~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~w_{0}$
$t = 1$	$(x_{2}+x_{1}+x_{0})\cdot (y_{2}+y_{1}+y_{0})$	$W(1)~~~=~~~~w_{4}+~w_{3}+~~w_{2}+~w_{1}+w_{0}$
$t = -1$	$(x_{2}-x_{1}+x_{0})\cdot (y_{2}-y_{1}+y_{0})$	$W(-1)~=~~~~w_{4}-~w_{3}+~~w_{2}-~w_{1}+w_{0}$
$t = 2$	$(4x_{2}+2x_{1}+x_{0})\cdot (4v_{2}+2v_{1}+y_{0})$	$L(2)~~~=~16v_{4}+8v_{3}+4v_{2}+2v_{1}+v_{0}$
$t=\infty$	$x_{2}\cdot y_{2}$	$W(\infty )~~=~~~~w_{4}$

Parametri on ehdollinen. Se tarkoittaa kertoimien banaalista yhtäläisyyttä kohdassa , joten saamme arvon välittömästi. Tämä järjestelmä on lineaarinen 5 tuntemattomassa. Kun se on ratkaistu, saamme tuntemattomia . Seuraavaksi saamme polynomin arvon edellä kuvatulla tavalla. $t=\infty$ $t^{4}$ $w_{4}$ $w_{i}$

Tooma-4 algoritmi

Algoritmin monimutkaisuus Edustaa 7 alkeiskertotoimintoa. Toom-4 jakaa syötteen 4 osaan. $O(n^{1.404}).$

Rakennamme kaksi polynomia samalla periaatteella kuin Toom-3:ssa:

X(t)=x3\cpiste t^{3}+x2\cpiste t^{2}+x1\cpiste t+x0,

Y(t)=y3\cdot t^{3}+y2\cdot t^{2}+y1\cdot t+y0.

$X(t)$ ja lasketaan 7 eri pisteessä, lasketaan myös arvo näissä kohdissa. $K(t)$ $W(t)$

$t = 0$	$x_{0}\cdot y_{0},$ mistä pääsemme heti $w_{0}$
$t = 1/2$	$(x_{3}+2x_{2}+4x_{1}+8x_{0})\cpiste (y_{3}+2v_{2}+4v_{1}+8v_{0})$
$t = -1/2$	$(-x_{3}+2x_{2}-4x_{1}+8x_{0})\cpiste (-y_{3}+2v_{2}-4v_{1}+8v_{0})$
$t = 1$	$(x_{3}+x_{2}+x_{1}+x_{0})\cpiste (y_{3}+y_{2}+y_{1}+y_{0})$
$t = -1$	$(-x_{3}+x_{2}-x_{1}+x_{0})\cdot (-y_{3}+y_{2}-y_{1}+y_{0})$
$t = 2$	$(8x_{3}+4x_{2}+2x_{1}+x_{0})\cpiste (8v_{3}+4v_{2}+2v_{1}+y_{0})$
$t=\infty$	$x_{3}\cdot y_{3},$ mistä pääsemme heti $w_{6}$

Toom-4:n yhteen- ja kertolaskuoperaatioiden määrä on paljon suurempi kuin Toom-3:n. Mutta jotkut ilmaisut esiintyvät useammin kuin kerran. Esimerkiksi laskettu ja [5] . $x_{2}+x_{0}$ $t = 1$ $t = -1$

Toomin algoritmi mielivaltaiselle osiolle

Toomin algoritmi syötettyjen lukujen jakamiseksi n:ksi operandiksi vastaa yllä kuvattua algoritmia. Yleensä kahden yhtä pitkän operandin jakaminen osiin johtaa pistearvojen laskemiseen . Pisteenä järjestelmän ratkaisemisesta he yleensä ottavat . $r$ $2r-1$ $0,\infty ,+1,-1,\pm 2^{i},\pm 2^{{-i}}$

Fourier-kertolasku

Tätä kertolaskualgoritmia käytetään suurille ja erittäin suurille luvuille [6] .

Tämä algoritmi kertoo kaksi numeroa ajassa, missä on kerrottujen lukujen merkitsevien numeroiden lukumäärä (olettaen, että ne ovat yhtä suuret). Luomisen syyksi ovat Cooley (Coolet) ja Tyuki (Tukey) - 1965. On myös ehdotuksia, että tämä algoritmi oli tunnettu aiemmin, mutta sillä ei ollut suurta merkitystä ennen ensimmäisten tietokoneiden keksimistä. Todennäköisiä ehdokkaita tämän algoritmin keksinnölle kutsutaan myös nimellä Runge (Runge) ja Koenig (Konig) - 1924 sekä Gauss - 1805. $O(n\cdot \log n),$ $n$

Olkoon luku, esitämme sen polynomina, kuten teimme aiemmin. Kutsutaan tätä polynomiksi . Esittelemme myös polynomin diskreetin Fourier-muunnoksen vektorina , jossa on koordinaatit . Missä määritetään - 1:n asteen kompleksijuuri , joka ei ole yhtä suuri kuin 1. Tosiasia on, että luvun 1 kompleksijuuri on määritelty vaihekertoimeen asti, näiden juurien lukumäärä on . Fourier-muunnosta käytetään polynomien kertoimien konvoluutio korvaamiseksi ja : - niiden Fourier-kuvien tulolla. $A(x).$ $\left(b_{1},b_{2},b_{3},b_{4},\dots b_{n-1}\right)$ $b[i]$ $w^{n}[i]$ $n$ $n$ $A$ $B$ $(A(x)\cdot B(x))$

F(A(x)\cdot B(x))=F(A)\cdot F(B)

A(x)\cdot B(x)=F^{-1}(F(A)\cdot F(B)),

jossa kertolasku tarkoittaa vektorien skalaarituloa. $F(A)\cdot F(B)$

Oletetaan, että on kahden potenssi. $n$

Löytäminen tapahtuu rekursiivisesti (hajota ja hallitse). Ajatuksena on jakaa alkuperäinen polynomi kahdeksi polynomiksi, $FA)$ ${\displaystyle A(x)=a_{0}x_{0}+a_{1}x_{1}+...+a_{n-1}x_{n-1))$

A0(x)=a_{0}x_{0}+a_{2}x_{1}+a_{4}x_{2}+\pisteet +a_{{n-2}}x_{{{\frac { n-2}{2}}}}

A1(x)=a_{1}x_{0}+a_{3}x_{1}+a_{5}x_{2}+\pisteet +a_{{n-1}}x_{{{\frac { n-2}{2}}}}

Sitten . $A(x)=A0(x^{2})+x\cdot A1(x^{2})$

Huomaa, että kaikista numeroista vain eri numerot. Siksi DFT on -elementti . Ja koska DFT koostuu elementeistä , niin luvun 1 kompleksijuuri on asteen juuri . $\left(w_{i}^{n}\right)^{2}(0\leq i<n)$ ${\frac {n}{2))$ $A0$ $A1$ ${\frac {n}{2))$ $A0$ $A1$ ${\frac {n}{2))$ ${\frac {n}{2))$

tarkoittaa,

A(w_{k}^{n})=A0(w_{2k}^{n})+w_{k}^{n}\cdot A1(w_{2k}^{n})=A0 (w_{k}^{\frac {n}{2}})+w_{k}^{n}\cdot A1(w_{k}^{\frac {n}{2}}),

missä ja $0\leq k<n/2$

A(w_{k+{\frac {n}{2))}^{n})=A0(w_{2\cdot {k+{\frac {n}{2))))^{n} )+w_{k+{\frac {n}{2}}}^{n}\cdot A1(w_{2\cdot {k+{\frac {n}{2}}}}^{n})=A0 (w_{k+{\frac {n}{2}}}^{n/2})+w_{k+{\frac {n}{2}}}^{n}\cdot A1(w_{k+{\ frac {n}{2}}}^{\frac {n}{2}})=A0(w_{k}^{\frac {n}{2}})-w_{k}^{n}\ cdot A1(w_{k}^{\frac {n}{2}}).

Käytimme kompleksilukujen ominaisuuksia: kaiken asteen eri juuria . . $n$ $n$ $w_{{k+{\frac {n}{2}}}}^{n}=w_{k}^{n}\cdot e^{{i\cdot {\frac {2\pi }{n}} \cdot {\frac {n}{2}}}}=w_{k}^{n}\cdot e^{{i\cdot \pi }}=-w_{k}^{n}$

Saamme rekursiivisen algoritmin:
yhden elementin DFT on yhtä suuri kuin tämä elementti
DFT A:n löytämiseksi, jaamme kertoimet A parillisiin ja parittoihin, saamme kaksi polynomia ja löydämme niille DFT:n, löydämme DFT:n. : varten . Seuraavasta väitteestä on todisteita: Käänteinen DFT löydetään samalla tavalla kuin suora DFT, paitsi että pisteet otetaan pisteiksi, jotka ovat symmetrisiä todellisen akselin suhteen, sen sijaan, että niitä käytetään suorassa DFT-muunnoksessa. On myös tarpeen jakaa kaikki polynomin kertoimet n:llä $A0$ $A1$ $A$
$b_{k}=b_{k}^{0}+w_{k}^{n}\cdot b_{k}^{1}$
$b_{{k+{\frac {n}{2}}}}=b_{k}^{0}-w_{k}^{n}\cdot b_{k}^{1}$
$0\leq k<n/2$

Juurenpoistoalgoritmit

Neliöjuuri

Yksi neliöjuurialgoritmeista on Karatsuba Square Root -algoritmi. Tämä on ylivoimaisesti tunnetuin menetelmä n - numeroisen luvun neliöjuuren laskemiseen. Tämä algoritmi käyttää nopeaa Fourier-muunnosta ja Newtonin menetelmää , jonka kompleksisuus on 5 M ( n ) [7] .

Esitetty algoritmi perustuu Burnickel-Ziegler (Burnikel-Ziegler) Karatsuban jakoon. Kun annetaan kokonaisluku n , algoritmi laskee samanaikaisesti sen kokonaisluvun neliöjuuren ja vastaavan jäännöksen, joka on Tämä ei ole asymptoottisesti optimaalinen, mutta käytännössä erittäin tehokas operaatioiden monimutkaisuuden järjestyksessä, missä K ( n ) on kertomiseen tarvittavien operaatioiden määrä kaksi n -bittistä numeroa käyttäen Karatsuba-algoritmia. Syynä tähän vähäiseen monimutkaisuuteen on Burnickelin ja Zieglerin äskettäin löytämä kaunis Karatsuba-divisioona ja jäännösten huolellinen käsittely, joka välttää turhat laskelmat. $s=\lfloor {\sqrt {n}}\rfloor$ $r=ns^{2}.$ ${\frac {3}{2}}K(n)$

Lause . SqrtRem-algoritmin käyttämien operaatioiden määrä 2n -bittisellä tulolla on rajoitettu

{\frac {3}{2}}K(n)+O(n\log n),

jossa K ( n ) on operaatioiden määrä, joka tarvitaan kertomaan 2 n -bittistä lukua käyttämällä Karatsuban algoritmia.

Algoritmi SqrtRem Input: kanssa Output: sellainen, että jos sitten palaa

(n=a_{3}b^{3}+a_{2}b^{2}+a_{1}b+a_{0})

0\leq a_{i}<b

a_{3}\geq b/4

{\näyttötyyli (s,r)}

s^{2}\leq n=s^{2}+r<(s+1)^{2}

(s',r')\leftarrow SqrtRem(a_{{3}}b+a_{{2}})

(q,u)\leftarrow DivRem(r'b+a_{{1}},2s')

s\leftarrow ub+a_{{0}}-q^{2}

r<0

r\leftarrow r+2s-1

s\leftarrow s-1

{\näyttötyyli (s,r)}

Algoritmit lukujärjestelmän muuntamiseen

Oletetaan, että olet muuntamassa kantaa b kanta B [8] .

Tapoja muuntaa kokonaislukuja

Menetelmä 1 (jako B:llä käyttämällä lukujen b-kantaesitystä). Tietylle kokonaisluvulle u voidaan
saada muodon B-kantamuodossa esitys tekemällä $(\dots U_{2}U_{1}U_{0})_{B}$

U_{0}=u\!\!\!\!\mod B

, , , asti .

U_{1}=\left\lfloor {\frac {u}{B}}\right\rfloor \!\!\!\!\mod B

U_{2}=\left\lfloor \left\lfloor {\frac {u}{B))\right\rfloor \right\rfloor \!\!\!\!\mod B

\left\lfloor \dots {\left\lfloor {\left\lfloor {\frac {u}{B))\right\rfloor }\right\rfloor }{\dots /B}\right\rfloor = 0

Menetelmä 2 (Kerto B:llä käyttämällä b-kantaesitystä). Jos luvun u esitys kannassa b on muotoa , niin käyttämällä aritmeettisia operaatioita lukujen kanssa, jotka esitetään muodossa B, voit saada polynomin muodossa (( . ${\näyttötyyli (u_{m}\pisteet u_{1}u_{0})_{b))$ $u_{m}b^{m}+\pisteet +u_{1}b+u_{m}u_{0}=u$
${\displaystyle \dots (u_{m}b+u_{m-1}){b}+\pisteet )b+u_{1}b+u_{0))$

Menetelmä 1 (a) (Kerto b:llä käyttämällä lukujen B-kantaesitystä). Tietylle murtoluvulle ja voit laskea sen esityksen numeroiden arvot kanta B:ssä seuraavasti: , , ,… missä {x} tarkoittaa xmod1 = x- . Tuloksen pyöristämiseksi M numeroon laskenta voidaan keskeyttää vastaanottamisen jälkeen , ja jos {…{{uВ}В}...В} on suurempi kuin 1/2, arvoa tulee suurentaa yhdellä. (Huomaa kuitenkin, että tämä operaatio voi johtaa tarpeeseen suorittaa käännöksiä, jotka tulisi sisällyttää tulokseen käyttämällä aritmeettisia operaatioita B-kannassa. Olisi helpompi lisätä vakio alkuperäiseen numeroon u ennen laskelmien aloittamista , mutta tämä voi johtaa virheelliseen tulokseen, jos tietokoneessa lukua ei voida esittää tarkasti kanta b -muodossa Huomaa myös, että tulos on mahdollista pyöristää muotoon if ). Menetelmä 2 (a) (Kerto B:llä käyttäen emäksen b esitystä). Jos luvun esitys kannassa b on muotoa , niin käyttämällä aritmeettisia operaatioita lukujen kanssa, jotka esitetään muodossa B-kanta, saat polynomin muodossa ((… + …) + . $(.U_{{-1}}U_{{-2}}...)_{{B}}$
$U_{{-1}}=\left\lfloor \ {uB}\right\rfloor$ $U_{{-2}}{=}\left\lfloor \ {{uB}B}\right\rfloor$ $U_{{-3}}=\left\lfloor \ {((uB)B)B}\right\rfloor$ $\left\lfloor \{x}\right\rfloor$ $U_{{M}}$ $U_{{M}}$ $1/2B^{{-M}}$ $1/2B^{{-M}}$ $(1,00...0)^{B}$ $b^{{m}}$ $\geq$ $2B^{{M}}$
$(u_{{m}}{...}u_{{1}}u_{{0}})_{{b}}$ $u_{{m}}b^{{m}}+{...}+u_{{1}}b+u_{{m}}u_{{0}}=u$
$(u_{{m}}b+u_{{m-1}}){b}$ $b$ $u_{{1}}b+u_{{0}}$

tapoja muuntaa murto-osia

Menetelmä 1 (b) (Kerto b:llä käyttämällä lukujen B-kantaesitystä). Tietylle murtoluvulle u voit laskea sen esityksen bittien arvot kantassa B seuraavasti: , , ,… missä {x} tarkoittaa xmod1 = x- . Tuloksen pyöristämiseksi M numeroon laskenta voidaan keskeyttää vastaanottamisen jälkeen , ja jos {…{{uВ}В}...В} on suurempi kuin 1/2, arvoa tulee suurentaa yhdellä. (Huomaa kuitenkin, että tämä operaatio voi johtaa tarpeeseen suorittaa käännöksiä, jotka tulisi sisällyttää tulokseen käyttämällä aritmeettisia operaatioita B-kannassa. Olisi helpompi lisätä vakio alkuperäiseen numeroon u ennen laskelmien aloittamista , mutta tämä voi johtaa virheelliseen tulokseen, jos tietokoneessa lukua ei voida esittää tarkasti kanta b -muodossa Huomaa myös, että tulos on mahdollista pyöristää muotoon if ). $(0.U_{{-1}}U_{{-2}}...)_{{B}}$
$U_{{-1}}=\left\lfloor \ {uB}\right\rfloor$ $U_{{-2}}{=}\left\lfloor \ {{uB}B}\right\rfloor$ $U_{{-3}}=\left\lfloor \ {((uB)B)B}\right\rfloor$ $\left\lfloor \{x}\right\rfloor$ $U_{{M}}$ $U_{{M}}$ $1/2B^{{-M}}$ $1/2B^{{-M}}$ $(1,00...0)^{B}$ $b^{{m}}$ $\geq$ $2B^{{M}}$

Menetelmä 2 (b) (jako b:llä käyttämällä lukujen B-kantaesitystä). Jos luku u esitetään kannassa b , niin käyttämällä aritmeettisia operaatioita kantassa B, se voidaan laskea muodossa . On tarpeen tarkkailla huolellisesti virheitä, joita esiintyy lyhennyksen tai pyöristyksen aikana jakamisen aikana b:llä; ne ovat yleensä merkityksettömiä, mutta näin ei aina ole. $(0.u_{{-1}}u_{{-2}}...u_{{-m}})_{{b}}$ $u_{{-1}}b^{{-1}}+u_{{-2}}b^{{-2}}+{...}+u_{{-m}}b{-m}$
$((...(u_{{-m}}/b+u_{{1-m}})/b+...+u_{{-2}})/b+u_{{-1}}) /b$

Multiple Precision Transformation

Erittäin pitkien lukujen muuntaminen on kätevintä aloittaa muuntamalla bittilohkoja, joiden toiminnot voidaan suorittaa yhdellä tarkkuudella. Yhdistät sitten nämä lohkot yksinkertaisilla menetelmillä, jotka ovat ominaisia useille tarkkuuksille. Olkoon esimerkiksi 10n suurin potenssi 10:llä pienempi kuin konesanan koko. Sitten:
a) Jos haluat muuntaa kokonaisluvun "Luku moninkertaisella tarkkuudella binääristä desimaaliin, se on kerrottava 10n:lla (siten muunnetaan binääriarvosta desimaaliksi kantaluvulla 10n käyttämällä menetelmää 1, a); käyttämällä operaatioita yhdellä tarkkuudella, saamme n desimaalin pistettä kullekin esitysyksikölle kantaluvussa 10n;
b) muuntaaksesi murto-osan "monitarkkuuden luvun binääriluvusta desimaaliksi, toimi samalla tavalla kertomalla se : lla: (eli menetelmällä 2, a, missä B \u003d 10n); c) Muuntaaksemme kokonaisluvun moninkertaisella tarkkuudella desimaaliluvusta binääriarvoksi muunnamme ensin n bitin lohkot; sitten muuntaaksesi kantasta 10n binääriseksi, käytä menetelmää 1, b; d) Jos haluat muuntaa moninkertaisen tarkkuuden murto-osan desimaalista binääriarvoksi, muunna ensin kantaluvuksi 10n kuten menettelyssä (c) ja käytä sitten menetelmää 2, b. $10^{n}$

Jakoalgoritmit

Algoritmin, jolla jaetaan n-bittinen luku u n-bittisellä luvulla v, on saatava kaksi n-bittistä lukua - u mod v ja u div v. Alla kuvatut algoritmit eivät sovellu käytännössä, koska ne löytävät jaon tuloksena reaaliluvun, ei kahta n-bittistä lukua.

Teoriassa n-bittisen luvun u jakamiseksi n-bittisellä luvulla v, voit ensin löytää n-bittisen approksimaatioluvun luvulle 1/v, sitten kertoa sen u:lla, mikä antaa likiarvon luvulle , ja lopuksi suorita toinen kertolasku tehdäksesi pienen korjauksen varmistaaksesi, että epäyhtälö pätee . Edellä olevan perusteella riittää, että on tehokas algoritmi, joka muodostaisi annetusta n-bittisestä luvusta likimääräisen arvon luvulle, joka on n-bittisen luvun käänteisarvo. Käytä seuraavaksi n-bittisten lukujen kertomisalgoritmia. [9] ${\hattu {q}}$ $u/v$ ${\hattu {q}}$ $0\leq u-qv<v$

Algoritmi R (käänteisluvun saaminen suurella tarkkuudella) Olkoon luvulla v binääriesitys , jossa . Tämä algoritmi laskee luvun likiarvon z siten, että . R1 (Alkuarvio) Määritä ja . R2 (Newton Iteration) Tässä meillä on numero z binäärimuodossa , jossa on jakopisteen ja jälkeiset merkit . Laske tarkasti käyttämällä nopeaa kertolaskuohjelmaa . Laske sen jälkeen tarkalleen missä . Määritä sitten , jossa , joka täyttää epäyhtälön , lisätään tarvittaessa pyöristämään niin, että se on :n kerrannainen . Ja lopuksi määrätä . R3 Jos , palaa vaiheeseen R2; muuten algoritmin suoritus päättyy. $v=(0.v_{{1}}v_{{2}}v_{{3}})_{{2}}$ $v_{{1}}=1$ $1/v$
$|z-1/v|\leq 2^{{-n}}$
$z\leftarrow {\frac {1}{4}}\left\lfloor {\frac {32}{(4v_{{1}}+2v_{{2}}+v_{{3}})))}\ oikea lattia$ $k\leftarrow 0$
$(xx.xx...x)_{{2}}$ $2^{k}+1$ $z\leq 2$ $z^{2}=(xx.xx...x)_{{2}}$ $V_{{k}}z^{2}$ $V_{{k}}=(0.v_{{1}}v_{{2}}...v_{{2^{{k+1}}+3}})_{{2}}$ $z\leftarrow 2z-V_{{k}}z^{2}+r$ $r$ $0\leq r<2^{{-2^{{k+1}}-1}}$ $z$ $z$ $2^{{-2^{{k+1}}-1}}$ $k\leftarrow k+1$
$2^{k}<n$

Muut algoritmit

Muistiinpanot

↑ 1 2 3 Richard P. Brent ja Paul Zimmermann, Modern Computer Aritmetic
↑ Donald E. Knuth "Tietokoneohjelmoinnin taito", kohta 4.3.1
↑ Donald E. Knuth "Tietokoneohjelmoinnin taito", osio 4.3.3, osa A
↑ Neuvostoliiton tiedeakatemian raportit 150 (1963), 496-498
↑ Toom 4-suuntainen kertolasku - GNU MP 5.1.3 . Haettu 13. joulukuuta 2013. Arkistoitu alkuperäisestä 14. maaliskuuta 2013. (määrätön)
↑ Donald E. Knuth "Tietokoneohjelmoinnin taito", osio 4.3.3, osa C
↑ Paul Zimmermann. Karatsuban neliöjuuri. [Tutkimusraportti] RR-3805, 1999, s.8. < inria-00072854 Arkistoitu 2. joulukuuta 2014 Wayback Machinessa >
↑ Donald E. Knuth "Tietokoneohjelmoinnin taito", osa 2, osa 4.4
↑ Donald E. Knuth "Tietokoneohjelmoinnin taito", osa 2, osa 4.3.3

Kirjallisuus

Donald E. Knuth, " The Art of Computer Programming ", osa 2, "Seminumerical Algorithms", 3. painos, Addison-Wesley, 1998
Dan Zuras, "Suurten kokonaislukujen neliöistämisestä ja kertomisesta", ARITH-11: IEEE Symposium on Computer Aithmetic, 1993, s. 260-271.
DAN SSSR 150 (1963), 496-498
Richard P. Brent ja Paul Zimmermann, Modern Computer Aithmetic
Sähköiset välineet ja ohjausjärjestelmät: Kansainvälisen tieteellisen ja käytännön konferenssin (13.-16.10.2010) raporttien aineisto. - Tomsk: V-Spectrum, 2011: Klo 2 tuntia - Osa 2. - 178 s. ISBN 978-5-91191-223-6, s. 123-129

Tietotyypit
Käsittämätön	Bitti Napostella Tavu qubit Kohdella Piirre Sana
Numeerinen	Koko kiinteä piste liukuluku Rationaalista Monimutkainen Pitkä intervalli
Teksti	Symbolinen merkkijono
Viite	Osoite Linkki Osoitin Kääre
Komposiitti	Algebrallinen tietotyyppi ( yleinen ) Luokka Tyyppituote ( Kirjoita Tuple rakenne ) Esine Konsolidointi ( tagged ) Järjestetty pari
abstrakti	joukko Lista Vuoro Pino Assosiatiivinen taulukko (näyttö, kartta ) Paljon multiset Tyyppi Kaavio
Muut	Looginen Alempi Korkeampi Polymorfinen Toimiva lueteltava Kokoelma Poikkeus Suku ( metaluokka ) Monad Semafori Virtaus mitätön
liittyvät aiheet	Abstrakti tietotyyppi primitiivinen tyyppi Tietorakenne Yleinen tyyppinen muuttuja Käyttöliittymä Rakentaja (OOP) Rakentaja (FP) Tyyppi rakentaja Tyyppivalu Prototyyppi Tyyppijärjestelmä