Lang aritmetik

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 21. januar 2022; checks kræver 2 redigeringer .

Lang aritmetik - aritmetiske operationer udført ved hjælp af en computer ( addition , subtraktion , multiplikation , division , eksponentiering , elementære funktioner ) på tal, hvis bitdybde overstiger længden af maskinordet på denne computer. Disse operationer implementeres ikke i hardware, men i software, ved at bruge den grundlæggende hardware til at arbejde med antallet af lavere ordrer. Et særligt tilfælde - arbitrær præcisionsaritmetik - refererer til aritmetik, hvor længden af tal kun er begrænset af mængden af tilgængelig hukommelse.

Ansøgning

Lang aritmetik bruges på følgende områder:

kompilering af kode til processorer ( mikrocontrollere ) med lav kapacitet . For eksempel har AVR -seriens mikrocontrollere en 10 - bit ADC og 8-bit registre . Dette er ikke nok til at behandle oplysninger fra ADC; lang aritmetik er uundværlig;
kryptografi . De fleste datasignerings- og krypteringssystemer bruger heltalsaritmetiske modulo m, hvor m er et meget stort naturligt tal, ikke nødvendigvis primtal . For eksempel, når man implementerer RSA- krypteringsmetoden , Rabin-kryptosystemet eller ElGamal-ordningen , er det påkrævet at sikre nøjagtigheden af resultaterne af multiplikation og eksponentiering i størrelsesordenen 10 309 ;
matematisk (se listen over software ) og finansiel software . Resultatet af beregningen på papir skal matche computerens resultat med det sidste ciffer. Især Windows-beregneren (siden Windows 95 ) udfører fire regneoperationer med meget større præcision, end x86- processoren tillader . Til videnskabelige og tekniske beregninger bruges der sjældent lang aritmetik, da fejlene i inputdataene normalt er meget større end afrundingsfejlene;
et standardemne i sportsprogrammering .

Nødvendig hardware for at arbejde med lang aritmetik

Strengt taget kræves kun indirekte adressering fra processoren for at implementere aritmetik med vilkårlig præcision ; i aritmetik med fast præcision kan du endda undvære det. Visse processorfunktioner fremskynder dog lang aritmetik, mens de forenkler programmeringen.

Bær flag . Operationer "tilføj / subtraher med carry", " roter gennem bærebitten ".
Indirekte adressering med auto-increment og auto-decrement (indeksregisteret øges eller dekrementeres efter operationen).
Multiplikation w · w = 2 w ( ord -for-ord multiplikation, resultat er et dobbeltord), division 2 w / w = w (med mulig overløb ).

Implementering i programmeringssprog

Programmeringssprog har indbyggede datatyper, der generelt ikke overstiger 64 bit (ca. 10 19 ). Decimal lang aritmetik blev implementeret i de sovjetiske programmeringssprog ALMIR-65 på MIR-1- computeren og ANALYTIK på MIR-2- computeren . For at arbejde med store tal er der i moderne programmeringssprog en del færdige optimerede biblioteker til lang aritmetik.

De fleste funktionelle sprog giver dig mulighed for at skifte fra almindelig aritmetik til lang aritmetik uden at skulle ændre den aritmetiske kode. For eksempel repræsenterer Erlang og Scheme altid nøjagtige tal så lange. I Standard ML bestemmes implementeringer af alle varianter af heltal baseret på signaturen INTEGER, hvilket giver dig mulighed for at vælge den nødvendige dimension, inklusive et modul IntInf, der implementerer heltal med vilkårlig præcision; PolyML-implementeringen bruger dette modul som standard.

Der er indbyggede biblioteker til at arbejde med store tal i PascalABC.NET, Ruby , Python og Java .

Algoritmer

Multiplikationsalgoritmer

Følgende repræsentation af heltal bruges normalt til at beskrive algoritmer. Basen er valgt . Så kan længdeheltallet repræsenteres som [1] : $\beta >1$ $n$

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

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

Grundlæggende

Det er en algoritme efter skolemetoden "i en kolonne". Det tager tid, hvor er størrelserne af de gangede tal. $O(n\cdot m),$ $n,m$

Algoritmen kan repræsenteres som [1] [2] :

Algoritme 1 BasecaseMultiply
Input: Output: for fra at gøre $A=\sum \nolimits _{{i=0}}^{{m-1}}a_{i}\beta ^{i},B=\sum \nolimits _{{j=0}}^{{ n-1}}b_{j}\beta ^{j}$
$C=AB:=\sum \nolimits _{{k=0}}^{{m+n-1}}c_{k}\beta ^{k}$
$1:C\får A\cdot b_{0}$
$2:$ $j$ $en$ $n-1$
$3:~~~~C\får C+\beta ^{j}(A\cdot b_{j})$
$4:retur~~C.$

Multiplikation af Karatsuba

Karatsubas multiplikationsmetode hører til " del og hersk " paradigmet. Beregningsmæssig kompleksitet af algoritmen:

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

Denne algoritme er en simpel implementering [3] af ideen om at opdele inputdata, som er blevet grundlaget for algoritmerne anført nedenfor. Ideen er at opdele en multiplikationsoperation på cifrede tal i tre multiplikationsoperationer på tal med længde plus [1] . $n$ $n/2$ $På)$

For at gange to tal større end et maskinord kaldes Karatsubas algoritme rekursivt, indtil tallene er små nok til at blive ganget direkte. Et eksempel på en sådan algoritme:

Algoritme 2 KaratsubaMultiply
Input: Output: KaratsubaMultiply KaratsubaMultiply KaratsubaMultiply $A=\sum \nolimits _{{i=0}}^{{n-1}}a_{i}\beta ^{i},B=\sum \nolimits _{{j=0}}^{{ n-1}}b_{j}\beta ^{j}$
$C=AB:=\sum \nolimits _{{k=0}}^{{2n-1}}c_{k}\beta ^{k}$
$k\får [n/2]$
$(A_{0},B_{0}):=(A,B)mod\beta ^{k},(A_{1},B_{1}):=(A,B)div\beta ^{k }$
$s_{A}\får tegn(A_{0}-A_{1}),s_{B}\får tegn(B_{0}-B_{1})$
$C_{0}\get$ $(A_{0},B_{0})$
$C_{1}\get$ $(A_{1},B_{1})$
$C_{2}\får$ $(|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}}$

Lad os tælle : $x=12345\cdot 6789$

12345=12\cdot 1000+345

6789=6\cdot 1000+789

Tre mellemliggende koefficienter skal beregnes:

C_{0}=345\cdot 789=272205

C_{1}=12\cdot 6=72

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

Resultat:

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

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

Toomas algoritme

Denne algoritme er en generalisering af Karatsuba-algoritmen og er hurtigere. Givet to heltal og , opdeler Tooms algoritme dem i mindre dele, som hver er lig med længden af et maskinord, og udfører operationer på disse dele. Beregningskompleksitet af algoritmen: $EN$ $B$ $k$ $O(n^{\ln(2k-1)/\ln(k)}).$

Tooma-3 algoritme

Ideen blev første gang foreslået af A. L. Toom i 1963 [4] , og består i at dele inputdataene (multiplikatorerne) i 3 lige store dele (for nemheds skyld betragtes alle dele som lige). Toom-3 reducerer antallet af elementære multiplikationsoperationer fra 9 til 5. Algoritmekompleksitet $O(n^{1.465}).$

Overvej denne algoritme i det følgende eksempel. Lad der være to tal og . Lad operationer defineres på tal, hvis størrelse er lig med 1/3 af størrelsen af de oprindelige tal (se figur). Vi antager også, at tallene optager lige stor hukommelse og er delelige med nøjagtigt 3 dele, ellers vil vi udfylde begge tal med nuller til den ønskede størrelse. $Y$ $x$

Derefter er der en afbildning (parametrisering) af disse dele til polynomier af 2. grad.

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

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

Lad os per definition introducere sådan, at værdierne af polynomierne er henholdsvis lig med inputtallene og . For en bitvis repræsentation af tal er dette tal to i potens lig med længden af hver del i bit. $b$ $X(b),~Y(b)$ $x$ $y$

Vi introducerer også et polynomium:

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

(en)

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

Efter at elementerne er bestemt - koefficienterne for polynomiet , vil de blive brugt for at opnå , da . Størrelsen af koefficienterne er 2 gange større (fra hukommelsen) end partitionen eller . Det endelige tal svarende til produktet kan findes ved at tilføje med et skift, som vist i figuren nedenfor. $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}$

Koefficienterne kan beregnes som følger: og så videre, men dette vil kræve alle 9 multiplikationer: for i, j=0,1,2, og vil svare til en simpel multiplikation. $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}$

I stedet valgte man en anden tilgang. beregnes i (1) ved 5 point for forskellige . $X(t),Y(t)$ $t$

Tabellen nedenfor viser værdierne af polynomierne i ligning (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 (4y_{2}+2y_{1}+y_{0})$	$W(2)~~~=~16w_{4}+8w_{3}+4w_{2}+2w_{1}+w_{0}$
$t=\infty$	$x_{2}\cdot y_{2}$	$W(\infty )~~=~~~~w_{4}$

Parameteren er betinget. Det betyder den banale lighed af koefficienterne ved , så vi får værdien med det samme. Dette system er lineært i 5 ubekendte. Når det er løst, får vi ubekendte . Dernæst får vi værdien af polynomiet, som beskrevet ovenfor. $t=\infty$ $t^{4}$ $w_{4}$ $w_{i}$

Tooma-4 algoritme

Algoritmens kompleksitet Repræsenterer 7 elementære multiplikationsoperationer. Toom-4 opdeler inputtet i 4 dele. $O(n^{1.404}).$

Efter samme princip som i Toom-3 bygger vi to polynomier:

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

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

$X(t)$ og beregnes ved 7 forskellige punkter, beregnes værdien på disse punkter også. $Y(t)$ $W(t)$

$t=0$	$x_{0}\cdot y_{0},$ hvorfra vi straks kommer $w_{0}$
$t=1/2$	$(x_{3}+2x_{2}+4x_{1}+8x_{0})\cdot (y_{3}+2y_{2}+4y_{1}+8y_{0})$
$t=-1/2$	$(-x_{3}+2x_{2}-4x_{1}+8x_{0})\cdot (-y_{3}+2y_{2}-4y_{1}+8y_{0})$
$t=1$	$(x_{3}+x_{2}+x_{1}+x_{0})\cdot (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})\cdot (8y_{3}+4y_{2}+2y_{1}+y_{0})$
$t=\infty$	$x_{3}\cdot y_{3},$ hvorfra vi straks kommer $w_{6}$

Antallet af additions- og multiplikationsoperationer for Toom-4 er meget større end for Toom-3. Men nogle udtryk forekommer mere end én gang. For eksempel beregnet for og for [5] . $x_{2}+x_{0}$ $t=1$ $t=-1$

Tooms algoritme for en vilkårlig partition

Tooms algoritme til at opdele inputtal i n operander svarer til den, der er beskrevet ovenfor. Generelt resulterer opdeling af to lige lange operander i dele i beregningen af prikværdier . Som point for løsning af systemet tager de normalt . $r$ $2r-1$ $0,\infty ,+1,-1,\pm 2^{i},\pm 2^{{-i}}$

Fourier multiplikation

Denne multiplikationsalgoritme bruges til store og meget store tal [6] .

Denne algoritme multiplicerer to tal i tid, hvor er antallet af signifikante cifre i de multiplicerede tal (forudsat at de er ens). Skabelsen tilskrives Cooley (Coolet) og Tyuki (Tukey) - 1965. Der er også forslag om, at denne algoritme var kendt før, men ikke var af stor betydning, før de første computere blev opfundet. Sandsynlige kandidater til forfatterskabet af opfindelsen af denne algoritme kaldes også Runge (Runge) og Koenig (Konig) - 1924, såvel som Gauss - 1805. $O(n\cdot \log n),$ $n$

Lad der være et tal, vi repræsenterer det som et polynomium, som vi gjorde tidligere. Lad os kalde dette polynomium Vi introducerer også den diskrete Fourier-transformation af polynomiet som en vektor , med koordinater . Hvor er defineret som - den komplekse rod af den th grad af 1, ikke lig med 1. Faktum er, at den komplekse rod af 1 er defineret op til en fasefaktor, antallet af disse rødder er . Fouriertransformationen anvendes for at erstatte foldningen af polynomiernes koefficienter og : - med produktet af deres Fourierbilleder. $A(x).$ $\left(b_{1},b_{2},b_{3},b_{4},\dots b_{n-1}\right)$ $b[i]$ $w^{n}[i]$ $n$ $n$ $EN$ $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)),

hvor multiplikation betyder skalarproduktet af vektorer. $F(A)\cdot F(B)$

Antag, at der er en potens af to. $n$

Finding sker rekursivt (del og hersk). Ideen er at opdele det oprindelige polynomium i to polynomier, $F(A)$ ${\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}+\dots +a_{{n-2}}x_{{{\frac { n-2}{2}}}}

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

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

Bemærk, at blandt alle numre kun forskellige. Derfor vil DFT være -element. Og da DFT består af elementer, så vil den komplekse rod af 1 der være roden af graden . $\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))$

Midler,

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}}),

hvor og $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}}).

Vi brugte egenskaberne ved komplekse tal: forskellige rødder af graden af alting . . $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}$

Vi får en rekursiv algoritme:
DFT for et element er lig med dette element
for at finde DFT A, vi deler koefficienterne A i lige og ulige, vi får to polynomier , og vi finder DFT for dem, vi finder DFT : for . Der er bevis for følgende udsagn: Den inverse DFT findes på samme måde som den direkte DFT, bortset fra at punkterne tages som punkter, der er symmetriske om den reelle akse, i stedet for dem, der bruges i den direkte DFT-transformation. Det er også nødvendigt at dividere alle polynomiets koefficienter med n $A0$ $A1$ $EN$
$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$

Rodekstraktionsalgoritmer

Kvadratrod

En af kvadratrodsalgoritmerne er Karatsuba Square Root-algoritmen. Dette er langt den bedst kendte metode til at beregne kvadratroden af et n -cifret tal. Denne algoritme bruger den hurtige Fourier-transformation og Newtons metode med kompleksitet 5 M ( n ) [7] .

Den præsenterede algoritme er baseret på opdelingen af Burnickel-Ziegler (Burnikel-Ziegler) Karatsuba. Givet et heltal n beregner algoritmen samtidig sin heltal kvadratrod og den tilsvarende rest, som er Dette er ikke asymptotisk optimalt, men meget effektivt i praksis med rækkefølge af operationer kompleksitet, hvor K ( n ) er antallet af operationer, der kræves for at multiplicere to n - bit-tal ved hjælp af Karatsuba-algoritmen. Årsagen til denne lave kompleksitet er den smukke Karatsuba-afdeling, der for nylig blev opdaget af Burnickel og Ziegler, og den omhyggelige håndtering af rester, der undgår unødvendige beregninger. $s=\lgulv {\sqrt {n}}\rgulv$ $r=ns^{2}.$ ${\frac {3}{2}}K(n)$

Sætning . Antallet af operationer, som SqrtRem-algoritmen bruger med en 2n - bit input, er begrænset

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

hvor K ( n ) er antallet af operationer, der kræves for at multiplicere 2 n -bit tal ved hjælp af Karatsubas algoritme.

Algoritme SqrtRem Input: med Output: sådan, at hvis derefter returnere

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

0\leq a_{i}<b

a_{3}\geq b/4

(s,r)

{\displaystyle 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

(s,r)

Algoritmer til konvertering af talsystemet

Antag, at du konverterer fra grundtal b til grundtal B [8] .

Måder at konvertere heltal

Metode 1 (Division med B ved hjælp af grundtal b repræsentation af tal). For et givet heltal u kan man
opnå en repræsentation i basis B-format af formen ved at gøre ${\displaystyle (\dots U_{2}U_{1}U_{0})_{B))$

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

, , , indtil .

U_{1}=\venstre\lgulv {\frac {u}{B}}\højre\rgulv \!\!\!\!\mod B

U_{2}=\venstre\lgulv \venstre\lgulv {\frac {u}{B))\højre\rgulv \højre\rgulv \!\!\!\!\mod B

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

Metode 2 (Multiplikation med B ved brug af base b-repræsentation). Hvis repræsentationen af tallet u i grundtallet b har formen , kan du ved hjælp af aritmetiske operationer med tal, der er repræsenteret i formatet i grundtallet B, få et polynomium på formen (( . ${\displaystyle (u_{m}\dots u_{1}u_{0})_{b))$ $u_{m}b^{m}+\dots +u_{1}b+u_{m}u_{0}=u$
${\displaystyle \dots (u_{m}b+u_{m-1}){b}+\dots )b+u_{1}b+u_{0))$

Metode 1 (a) (Multiplikation med b ved hjælp af basis B-repræsentation af tal). For et givet brøktal og du kan beregne værdierne af cifrene i dets repræsentation i basis B som følger: , , ,... hvor {x} betyder xmod1 = x- . For at afrunde resultatet til M cifre kan beregningen afbrydes efter modtagelse af , og hvis {...{{uВ}В}...В} er større end 1/2, så skal værdien øges med én. (Bemærk dog, at denne operation kan føre til behovet for at udføre oversættelser, som bør inkluderes i resultatet ved hjælp af aritmetiske operationer i basis B. Det ville være nemmere at tilføje en konstant til det oprindelige tal u, før du starter beregningerne , men dette kan føre til et forkert resultat, hvis tallet i en computer ikke kan repræsenteres nøjagtigt i basis b-format Bemærk også, at det er muligt at afrunde resultatet til if ). Metode 2 (a) (Multiplikation med B ved brug af base b-repræsentation). Hvis repræsentationen af et tal og i grundtal b har formen , så ved hjælp af aritmetiske operationer med tal, der er præsenteret i formatet i grundtal B, kan du få et polynomium på formen ((… + …) + . $(.U_{{-1}}U_{{-2}}...)_{{B}}$
$U_{{-1}}=\venstre\lgulv \ {uB}\højre\rgulv$ $U_{{-2}}{=}\venstre\lgulv \ {{uB}B}\højre\rgulv$ $U_{{-3}}=\venstre\lgulv \ {((uB)B)B}\højre\rgulv$ $\venstre\lgulv \{x}\højre\rgulv$ $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}}$

Måder at konvertere brøktal på

Metode 1 (b) (Multiplikation med b ved brug af basis B-repræsentation af tal). For et givet brøktal u kan du beregne værdierne af bits af dets repræsentation i basis B som følger: , , ,... hvor {x} betyder xmod1 = x- . For at afrunde resultatet til M cifre kan beregningen afbrydes efter modtagelse af , og hvis {...{{uВ}В}...В} er større end 1/2, så skal værdien øges med én. (Bemærk dog, at denne operation kan føre til behovet for at udføre oversættelser, som bør inkluderes i resultatet ved hjælp af aritmetiske operationer i basis B. Det ville være nemmere at tilføje en konstant til det oprindelige tal u, før du starter beregningerne , men dette kan føre til et forkert resultat, hvis tallet i en computer ikke kan repræsenteres nøjagtigt i basis b-format Bemærk også, at det er muligt at afrunde resultatet til if ). $(0.U_{{-1}}U_{{-2}}...)_{{B}}$
$U_{{-1}}=\venstre\lgulv \ {uB}\højre\rgulv$ $U_{{-2}}{=}\venstre\lgulv \ {{uB}B}\højre\rgulv$ $U_{{-3}}=\venstre\lgulv \ {((uB)B)B}\højre\rgulv$ $\venstre\lgulv \{x}\højre\rgulv$ $U_{{M}}$ $U_{{M}}$ $1/2B^{{-M}}$ $1/2B^{{-M}}$ $(1,00...0)^{B}$ $b^{{m}}$ $\geq$ $2B^{{M}}$

Metode 2 (b) (Division med b ved hjælp af grund B-repræsentation af tal). Hvis tallet u er repræsenteret i grundtallet b som , så ved hjælp af aritmetiske operationer i grundtallet B, kan det beregnes som . Det er nødvendigt omhyggeligt at overvåge de fejl, der opstår ved trunkering eller afrunding under divisionsoperationen med b; de er normalt ubetydelige, men det er ikke altid tilfældet. $(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

Det er mest bekvemt at begynde at konvertere meget lange tal ved at konvertere blokke af bit, som kan udføres med enkelt præcision. Du kombinerer derefter disse blokke ved hjælp af simple metoder, der er specifikke for multipel præcision. Lad f.eks. 10n være den højeste potens af 10 mindre end maskinordstørrelsen. Derefter:
a) for at konvertere et heltal "Tal med multiple præcision fra binært til decimaltal, er det nødvendigt at gange det med 10n (altså konvertere fra binært til decimaltal med grundtal 10n ved hjælp af metode 1, a); ved at bruge operationer med en enkelt præcision, vi får n decimaler for hver repræsentationsenhed i grundtallet 10n;
b) for at konvertere brøkdelen "Del af et tal med flere præcision fra binært til decimaltal, fortsæt på lignende måde ved at gange det med : (dvs. ved at bruge metode 2, a, hvor B \u003d 10n); c) for at konvertere et heltal med multiple præcision fra decimal til binær, konverterer vi først blokke af n bit; derefter, for at konvertere fra basis 10n til binær, brug metode 1, b; d) For at konvertere en brøkdel med flere præcision fra decimal til binær skal du først konvertere til grundtal 10n som i procedure (c) og derefter bruge metode 2, b. $10^{n}$

Divisionsalgoritmer

Algoritmen til at dividere et n-bit tal u med et n-bit tal v skal resultere i to n-bit tal - u mod v og u div v. Algoritmerne beskrevet nedenfor er ikke anvendelige i praksis, da de finder et reelt tal, og ikke to n-bit tal, resultatet af division.

I teorien, for at dividere et n-bit tal u med et n-bit tal v, kan du først finde en n-bit tilnærmelse til tallet 1/v, derefter gange det med u, hvilket vil give en tilnærmelse til , og til sidst udfør endnu en multiplikation for at lave en lille korrektion for at sikre, at uligheden holder . Baseret på det foregående er det nok at have en effektiv algoritme, der ud fra et givet n-bit tal ville danne en omtrentlig værdi af det tal, der er den inverse af et n-bit tal. Anvend derefter algoritmen til at multiplicere n-bit tal. [9] ${\hat {q))$ $u/v$ ${\hat {q))$ $0\leq u-qv<v$

Algoritme R (Opnåelse af den reciproke med høj præcision) Lad tallet v har en binær repræsentation , hvor . Denne algoritme beregner en tilnærmelse z af tallet , således at . R1 (Oprindeligt gæt) Tildel og . R2 (Newton Iteration) Her har vi tallet z i binær form med fortegn efter delepunktet og . Beregn nøjagtigt ved hjælp af det hurtige multiplikationsprogram . Beregn derefter præcis hvor . Derefter tildele , hvor , som opfylder uligheden , tilføjes efter behov for at afrunde , så det er et multiplum af . Og til sidst tildele . R3 Hvis , så vend tilbage til trin R2; ellers slutter udførelsen af algoritmen. $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}})))}\ højre gulv$ $k\venstrepil 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\venstrepil 2z-V_{{k}}z^{2}+r$ $r$ $0\leq r<2^{{-2^{{k+1}}-1}}$ $z$ $z$ $2^{{-2^{{k+1}}-1}}$ $k\venstrepil k+1$
$2^{k}<n$

Andre algoritmer

Noter

↑ 1 2 3 Richard P. Brent og Paul Zimmermann, Modern Computer Arithmetic
↑ Donald E. Knuth "Kunsten at programmere computer", afsnit 4.3.1
↑ Donald E. Knuth "Kunsten at programmere computer", afsnit 4.3.3, del A
↑ Rapporter fra USSRs Videnskabsakademi 150 (1963), 496-498
↑ Toom 4-vejs multiplikation - GNU MP 5.1.3 . Hentet 13. december 2013. Arkiveret fra originalen 14. marts 2013. (ubestemt)
↑ Donald E. Knuth "Kunsten at programmere computer", afsnit 4.3.3, del C
↑ Paul Zimmermann. Karatsuba kvadratrod. [Forskningsrapport] RR-3805, 1999, s.8. < inria-00072854 Arkiveret 2. december 2014 på Wayback Machine >
↑ Donald E. Knuth "Kunsten at programmere computer", bind 2, afsnit 4.4
↑ Donald E. Knuth "The Art of Computer Programming", bind 2, afsnit 4.3.3

Litteratur

Donald E. Knuth, " The Art of Computer Programming ", bind 2, "Seminumerical Algorithms", 3. udgave, Addison-Wesley, 1998
Dan Zuras, "Om kvadrering og multiplikation af store heltal", ARITH-11: IEEE Symposium on Computer Arithmetic, 1993, s. 260 til 271.
DAN SSSR 150 (1963), 496-498
Richard P. Brent og Paul Zimmermann, Modern Computer Arithmetic
Elektroniske midler og kontrolsystemer: Proceedings of the reports of the International Scientific and Practical Conference (13.-16. oktober 2010). - Tomsk: V-Spectrum, 2011: Ved 2 timer - Del 2. - 178 s. ISBN 978-5-91191-223-6 , s.123-129

Datatyper
Ufortolkelig	Bit Nappe Byte qubit Behandle Egenskab Ord
Numerisk	Hel fast punkt flydende komma Rationel Kompleks Lang interval
Tekst	Symbolsk Snor
Reference	Adresse Link Pointer Indpakning
Sammensatte	Algebraisk datatype ( generisk ) Klasse Type-produkt ( Skriv Tuple struktur ) Et objekt Konsolidering ( tagget ) Bestilt par
abstrakt	array Liste Tur Stak Associativ array (visning, kort ) Masser af multisæt Type Kurve
Andet	Logisk Nederste Højere Polymorf Funktionel talløse Kollektion Undtagelse Slægt ( metaklasse ) Monade Semafor Flyde ugyldig
relaterede emner	Abstrakt datatype primitiv type Datastruktur Generisk type variabel Interface Konstruktør (OOP) Konstruktør (FP) Type konstruktør Type støbning Prototype Type system