Lång aritmetik

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 21 januari 2022; kontroller kräver 2 redigeringar .

Lång aritmetik - aritmetiska operationer som utförs med hjälp av en dator ( addition , subtraktion , multiplikation , division , exponentiering , elementära funktioner ) på tal vars bitdjup överstiger längden på maskinordet i denna dator. Dessa operationer implementeras inte i hårdvara, utan i mjukvara, med hjälp av den grundläggande hårdvaran för att arbeta med antal lägre beställningar. Ett specialfall - godtycklig precisionsaritmetik - hänvisar till aritmetik där längden på siffror endast begränsas av mängden tillgängligt minne.

Applikation

Lång aritmetik används inom följande områden:

kompilering av kod för processorer ( mikrokontroller ) med låg kapacitet . Till exempel har AVR -seriens mikrokontroller en 10 -bitars ADC och 8-bitars register . Detta är inte tillräckligt för att bearbeta information från ADC; lång aritmetik är oumbärlig;
kryptografi . De flesta datasignerings- och krypteringssystem använder heltalsaritmetiska modulo m, där m är ett mycket stort naturligt tal, inte nödvändigtvis primtal . Till exempel, när man implementerar RSA-krypteringsmetoden , Rabins kryptosystem eller ElGamal -schemat , krävs det att man säkerställer noggrannheten hos resultaten av multiplikation och exponentiering i storleksordningen 10 309 ;
matematisk (se listan över programvara ) och finansiell programvara . Resultatet av beräkningen på papper måste matcha datorns resultat med den sista siffran. Framför allt utför Windows-kalkylatorn (sedan Windows 95 ) fyra aritmetiska operationer med mycket större precision än vad x86- processorn tillåter . För vetenskapliga och tekniska beräkningar används sällan lång aritmetik, eftersom felen i indata vanligtvis är mycket större än avrundningsfelen;
ett standardämne inom sportprogrammering .

Hårdvara som krävs för att arbeta med lång aritmetik

Strängt taget krävs endast indirekt adressering från processorn för att implementera aritmetik med godtycklig precision ; i aritmetik med fast precision kan du till och med klara dig utan den. Vissa processorfunktioner påskyndar dock lång aritmetik samtidigt som de förenklar programmeringen.

Bär flagga . Operationerna "lägg till / subtrahera med bär", " rotera genom bärbiten ".
Indirekt adressering med auto-increment och auto-decrement (indexregistret ökas eller minskas efter operationen).
Multiplikation w · w = 2 w ( ord -för-ord multiplikation, resultatet är ett dubbelord), division 2 w / w = w (med eventuellt spill ).

Implementering i programmeringsspråk

Programmeringsspråk har inbyggda datatyper som i allmänhet inte överstiger 64 bitar (cirka 10 19 ). Decimal lång aritmetik implementerades i de sovjetiska programmeringsspråken ALMIR-65 på MIR-1- datorn och ANALYTIK på MIR-2- datorn . För att arbeta med stora siffror finns det i moderna programmeringsspråk en hel del färdiga optimerade bibliotek för lång aritmetik.

De flesta funktionella språk låter dig byta från vanlig aritmetik till lång aritmetik utan att behöva ändra den aritmetiska koden. Till exempel representerar Erlang och Schema alltid exakta siffror så långa. I Standard ML bestäms implementeringar av alla varianter av heltal baserat på signaturen INTEGER, vilket gör att du kan välja önskad dimension, inklusive en modul IntInfsom implementerar heltal med godtycklig precision; PolyML-implementeringen använder denna modul som standard.

Det finns inbyggda bibliotek för att arbeta med stora siffror i PascalABC.NET, Ruby , Python och Java .

Algoritmer

Multiplikationsalgoritmer

Följande representation av heltal används vanligtvis för att beskriva algoritmer. Basen är vald . Sedan kan längdheltalet representeras som [1] : $\beta >1$ $n$

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

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

Grundläggande

Det är en algoritm enligt skolmetoden "i en kolumn". Det tar tid var är storleken på de multiplicerade talen. $O(n\cdot m),$ $n,m$

Algoritmen kan representeras som [1] [2] :

Algoritm 1 BasecaseMultiply
Input: Output: för från att göra $A=\summa \nolimits _{{i=0}}^{{m-1}}a_{i}\beta ^{i},B=\summa \nolimits _{{j=0}}^{{ n-1}}b_{j}\beta ^{j}$
$C=AB:=\summa \nolimits _{{k=0}}^{{m+n-1}}c_{k}\beta ^{k}$
$1:C\får A\cdot b_{0}$
$2:$ $j$ $ett$ $n-1$
$3:~~~~C\får C+\beta ^{j}(A\cdot b_{j})$
$4:retur~~C.$

Multiplikation av Karatsuba

Karatsubas multiplikationsmetod tillhör paradigmet " dela och erövra ". Algoritmens beräkningskomplexitet :

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

Denna algoritm är en enkel implementering [3] av idén om att dela upp indata, som har blivit grunden för algoritmerna som listas nedan. Tanken är att dela upp en multiplikationsoperation på siffriga tal i tre multiplikationsoperationer på tal med längd plus [1] . $n$ $n/2$ $På)$

För att multiplicera två tal större än ett maskinord, kallas Karatsubas algoritm rekursivt tills talen är tillräckligt små för att kunna multipliceras direkt. Ett exempel på en sådan algoritm:

Algoritm 2 KaratsubaMultiply
Input: Output: KaratsubaMultiply KaratsubaMultiply KaratsubaMultiply $A=\summa \nolimits _{{i=0}}^{{n-1}}a_{i}\beta ^{i},B=\summa \nolimits _{{j=0}}^{{ n-1}}b_{j}\beta ^{j}$
$C=AB:=\summa \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 tecken(A_{0}-A_{1}),s_{B}\får tecken(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}}$

Låt oss räkna : $x=12345\cdot 6789$

12345=12\cdot 1000+345

6789=6\cdot 1000+789

Tre mellanliggande koefficienter måste beräknas:

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 algoritm

Denna algoritm är en generalisering av Karatsuba-algoritmen och är snabbare. Med tanke på två heltal och , delar Tooms algoritm upp dem i mindre delar, som var och en är lika med längden på ett maskinord, och utför operationer på dessa delar. Beräkningskomplexitet för algoritmen: $A$ $B$ $k$ $O(n^{\ln(2k-1)/\ln(k)}).$

Tooma-3 algoritm

Idén föreslogs först av A. L. Toom 1963 [4] , och består i att dela in indata (multiplikatorer) i 3 lika delar (för enkelhetens skull anses alla delar vara lika). Toom-3 minskar antalet elementära multiplikationsoperationer från 9 till 5. Algoritmkomplexitet $O(n^{1.465}).$

Betrakta denna algoritm i följande exempel. Låt det vara två siffror och . Låt operationer definieras på tal vars storlek är lika med 1/3 av storleken på de ursprungliga talen (se figur). Vi antar också att talen upptar lika mycket minne och är delbara med exakt 3 delar, annars fyller vi båda talen med nollor till önskad storlek. $Y$ $X$

Sedan sker en mappning (parametrisering) av dessa delar till polynom av 2:a graden.

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

Låt oss introducera , per definition, så att polynomens värden är lika med ingångstalen respektive . För en bitvis representation av siffror är detta nummer två i potens lika med längden av varje del i bitar. $b$ $X(b),~Y(b)$ $x$ $y$

Vi introducerar också ett polynom:

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

(ett)

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

Efter att elementen har bestämts - koefficienterna för polynomet , kommer de att användas för att erhålla , eftersom . Storleken på koefficienterna är 2 gånger större (från minnet) än partitionen eller . Det slutliga numret som är lika med produkten kan hittas genom att lägga till med ett skift, som visas i figuren nedan. $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}$

Koefficienterna kan beräknas enligt följande: och så vidare, men detta kommer att kräva alla 9 multiplikationer: för i, j=0,1,2, och kommer att vara ekvivalent med en enkel 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}$

Istället togs ett annat grepp. beräknas i (1) till 5 poäng för olika . $X(t),Y(t)$ $t$

Tabellen nedan visar värdena för polynomen i ekvation (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}$

Parametern är villkorad. Det betyder den banala likheten av koefficienterna vid , så vi kommer att få värdet omedelbart. Detta system är linjärt i 5 okända. När det är löst får vi okända . Därefter får vi värdet på polynomet, som beskrivits ovan. $t=\infty$ $t^{4}$ $w_{4}$ $w_{i}$

Tooma-4 algoritm

Algoritmens komplexitet representerar 7 elementära multiplikationsoperationer. Toom-4 delar upp ingången i 4 delar. $O(n^{1.404}).$

Enligt samma princip som i Toom-3 bygger vi två polynom:

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)$ och beräknas vid 7 olika punkter, beräknas även värdet på dessa punkter. $Y(t)$ $W(t)$

$t=0$	$x_{0}\cdot y_{0},$ varifrån vi omedelbart 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},$ varifrån vi omedelbart kommer $w_{6}$

Antalet additions- och multiplikationsoperationer för Toom-4 är mycket större än för Toom-3. Men vissa uttryck förekommer mer än en gång. Till exempel beräknat för och för [5] . $x_{2}+x_{0}$ $t=1$ $t=-1$

Tooms algoritm för en godtycklig partition

Tooms algoritm för att dela in ingångsnummer i n operander är likvärdig med den som beskrivs ovan. Generellt sett resulterar en uppdelning av två lika långa operander i delar i beräkningen av punktvärden . Som poäng för att lösa systemet tar de vanligtvis . $r$ $2r-1$ $0,\infty ,+1,-1,\pm 2^{i},\pm 2^{{-i}}$

Fouriermultiplikation

Denna multiplikationsalgoritm används för stora och mycket stora tal [6] .

Denna algoritm multiplicerar två tal i tiden där är antalet signifikanta siffror i de multiplicerade talen (förutsatt att de är lika). Skapelsen tillskrivs Cooley (Coolet) och Tyuki (Tukey) - 1965. Det finns också förslag på att denna algoritm var känd tidigare, men inte var av stor betydelse innan de första datorerna uppfanns. Troliga kandidater för författarskapet till uppfinningen av denna algoritm kallas också Runge (Runge) och Koenig (Konig) - 1924, såväl som Gauss - 1805. $O(n\cdot \log n),$ $n$

Låt det finnas ett tal, vi representerar det som ett polynom, som vi gjorde tidigare. Låt oss kalla detta polynom Vi introducerar också den diskreta Fouriertransformen av polynomet som en vektor , med koordinater . Där definieras som - den komplexa roten av den e graden av 1, inte lika med 1. Faktum är att den komplexa roten av 1 definieras upp till en fasfaktor, antalet av dessa rötter är . Fouriertransformen tillämpas för att ersätta faltningen av polynomens koefficienter och : - med produkten av deras Fourierbilder. $A(x).$ $\left(b_{1},b_{2},b_{3},b_{4},\dots b_{n-1}\right)$ $bi]$ $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)),

där multiplikation betyder skalärprodukten av vektorer. $F(A)\cdot F(B)$

Anta att det finns en tvåpotens. $n$

Att hitta görs rekursivt (dela och härska). Tanken är att dela upp det ursprungliga polynomet i två polynom, $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}+\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}}}}

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

Observera att bland alla nummer , bara olika. Därför kommer DFT att vara -element. Och eftersom DFT består av element, kommer den komplexa roten av 1 att vara roten till 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))$

Betyder att,

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

var och $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 använde egenskaperna hos komplexa tal: olika rötter av graden av allt . . $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 algoritm:
DFT för ett element är lika med detta element
för att hitta DFT A, vi delar upp koefficienterna A i jämna och udda, vi får två polynom och , vi hittar DFT för dem, vi hittar DFT : för . Det finns bevis för följande påstående: Den inversa DFT hittas på samma sätt som den direkta DFT, förutom att punkterna tas som punkter som är symmetriska kring den reella axeln, istället för de som används i den direkta DFT-transformationen. Det är också nödvändigt att dividera alla koefficienter för polynomet med n $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$

Rotextraktionsalgoritmer

Kvadratrot

En av kvadratrotsalgoritmerna är Karatsuba Square Root-algoritmen. Detta är den i särklass mest kända metoden för att beräkna kvadratroten ur ett n -siffrigt tal. Denna algoritm använder den snabba Fouriertransformen och Newtons metod med komplexitet 5 M ( n ) [7] .

Den presenterade algoritmen är baserad på uppdelningen av Burnickel-Ziegler (Burnikel-Ziegler) Karatsuba. Givet ett heltal n , beräknar algoritmen samtidigt sin heltalskvadratrot och motsvarande återstod, vilket är Detta är inte asymptotiskt optimalt, men mycket effektivt i praktiken med operationsordningskomplexitet, där K ( n ) är antalet operationer som krävs för att multiplicera två n -bitars nummer med hjälp av Karatsuba-algoritmen. Anledningen till denna låga komplexitet är den vackra Karatsuba-divisionen som nyligen upptäckts av Burnickel och Ziegler, och den noggranna hanteringen av rester som undviker onödiga beräkningar. $s=\lfloor {\sqrt {n}}\rfloor$ $r=ns^{2}.$ ${\frac {3}{2}}K(n)$

Teorem . Antalet operationer som SqrtRem-algoritmen använder med en 2n -bitars ingång är begränsat

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

där K ( n ) är antalet operationer som krävs för att multiplicera 2 n -bitars tal med hjälp av Karatsubas algoritm.

Algoritm SqrtRem Input: med Output: sådan att om sedan returnera

(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)

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 för att konvertera talsystemet

Antag att du konverterar från bas b till bas B [8] .

Sätt att konvertera heltal

Metod 1 (Division med B med bas b representation av tal). För ett givet heltal u kan man
få en representation i bas B-format av formen genom att göra $(\dots U_{2}U_{1}U_{0})_{B}$

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

, , , tills .

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

Metod 2 (Multiplikation med B med bas b-representation). Om representationen av talet u i bas b har formen , då med aritmetiska operationer med tal som representeras i formatet i bas B, kan du få ett polynom i 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))$

Metod 1 (a) (Multiplikation med b med bas B-representation av tal). För ett givet bråktal och du kan beräkna värdena för siffrorna i dess representation i bas B enligt följande: , , ,... där {x} betyder xmod1 = x- . För att avrunda resultatet till M siffror kan beräkningen avbrytas efter att ha tagits emot , och om {...{{uВ}В}...В} är större än 1/2, så bör värdet ökas med ett. (Observera dock att denna operation kan leda till behovet av att utföra översättningar, vilket bör inkluderas i resultatet med aritmetiska operationer i bas B. Det skulle vara lättare att lägga till en konstant till det ursprungliga talet u innan beräkningarna påbörjas , men detta kan leda till ett felaktigt resultat, om talet i en dator inte kan representeras exakt i bas b-format Observera också att det är möjligt att avrunda resultatet till if ). Metod 2 (a) (Multiplikation med B med bas b-representation). Om representationen av ett tal och i bas b har formen , då med aritmetiska operationer med tal som presenteras i formatet i bas B, kan du få ett polynom i formen ((… + …) + . $(.U_{{-1}}U_{{-2}}...)_{{B}}$
$U_{{-1}}=\vänster\lgolv \ {uB}\höger\rgolv$ $U_{{-2}}{=}\vänster\lgolv \ {{uB}B}\höger\rgolv$ $U_{{-3}}=\vänster\lgolv \ {((uB)B)B}\höger\rgolv$ $\vänster\lgolv \{x}\höger\rgolv$ $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}}$

Sätt att konvertera bråktal

Metod 1 (b) (Multiplikation med b med bas B-representation av tal). För ett givet bråktal u kan du beräkna värdena för bitarna i dess representation i bas B enligt följande: , , ,... där {x} betyder xmod1 = x- . För att avrunda resultatet till M siffror kan beräkningen avbrytas efter att ha tagits emot , och om {...{{uВ}В}...В} är större än 1/2, så bör värdet ökas med ett. (Observera dock att denna operation kan leda till behovet av att utföra översättningar, vilket bör inkluderas i resultatet med aritmetiska operationer i bas B. Det skulle vara lättare att lägga till en konstant till det ursprungliga talet u innan beräkningarna påbörjas , men detta kan leda till ett felaktigt resultat, om talet i en dator inte kan representeras exakt i bas b-format Observera också att det är möjligt att avrunda resultatet till if ). $(0.U_{{-1}}U_{{-2}}...)_{{B}}$
$U_{{-1}}=\vänster\lgolv \ {uB}\höger\rgolv$ $U_{{-2}}{=}\vänster\lgolv \ {{uB}B}\höger\rgolv$ $U_{{-3}}=\vänster\lgolv \ {((uB)B)B}\höger\rgolv$ $\vänster\lgolv \{x}\höger\rgolv$ $U_{{M}}$ $U_{{M}}$ $1/2B^{{-M}}$ $1/2B^{{-M}}$ $(1.00...0)^{B}$ $b^{{m}}$ $\geq$ $2B^{{M}}$

Metod 2 (b) (Division med b med bas B-representation av tal). Om talet u representeras i basen b som , då med aritmetiska operationer i basen B, kan det beräknas som . Det är nödvändigt att noggrant övervaka de fel som uppstår vid trunkering eller avrundning under divisionsoperationen med b; de är vanligtvis obetydliga, men så är inte alltid fallet. $(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 är mest bekvämt att börja konvertera mycket långa tal genom att konvertera block av bitar, operationer som kan utföras med enkel precision. Du kombinerar sedan dessa block med enkla metoder som är specifika för multipel precision. Låt till exempel 10n vara den högsta potensen av 10 mindre än maskinordstorleken. Sedan:
a) för att konvertera ett heltal "Tal med multipel precision från binärt till decimalt, är det nödvändigt att multiplicera det med 10n (därmed konvertera från binärt till decimalt med basen 10n med hjälp av metod 1, a); använda operationer med en enda precision, vi får n decimaler för varje representationsenhet i basen 10n;
b) för att omvandla bråktalet "Del av ett tal med flera precision från binärt till decimalt, fortsätt på liknande sätt genom att multiplicera det med : (dvs. med metod 2, a, där B \u003d 10n); c) för att konvertera ett heltal med multipel precision från decimal till binär, konverterar vi först block med n bitar; använd sedan metod 1, b för att konvertera från bas 10n till binär; d) För att konvertera en bråkdel med multipel precision från decimal till binär, konvertera först till bas 10n som i procedur (c) och använd sedan metod 2, b. $10^{n}$

Divisionsalgoritmer

Algoritmen för att dividera ett n-bitars tal u med ett n-bitars tal v måste resultera i två n-bitars tal - u mod v och u div v. Algoritmerna som beskrivs nedan är inte tillämpliga i praktiken, eftersom de hittar ett reellt tal, och inte två n-bitars tal, resultatet av division.

I teorin, för att dividera ett n-bitars tal u med ett n-bitars tal v, kan du först hitta en n-bitars approximation till talet 1/v, sedan multiplicera det med u, vilket ger en approximation till , och slutligen utför ytterligare en multiplikation för att göra en liten korrigering för att se till att ojämlikheten håller . Baserat på det föregående räcker det att ha en effektiv algoritm som skulle bilda, från ett givet n-bitars tal, ett ungefärligt värde på talet som är inversen av ett n-bitars tal. Använd sedan algoritmen för att multiplicera n-bitars tal. [9] ${\hat {q}}$ $u/v$ ${\hat {q}}$ $0\leq u-qv<v$

Algoritm R (Erhålla den reciproka med hög precision) Låt talet v har en binär representation , där . Denna algoritm beräknar en approximation z av talet så att . R1 (Initial gissning) Tilldela och . R2 (Newton Iteration) Här har vi talet z i binär form med tecken efter delningspunkten och . Beräkna exakt med det snabba multiplikationsprogrammet . Efter det beräkna exakt var . Sedan tilldela , där , som uppfyller olikheten , läggs till vid behov för att avrunda så att det är en multipel av . Och slutligen tilldela . R3 Om , gå tillbaka till steg R2; annars avslutas exekveringen av 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öger golv$ $k\vänsterpil 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\vänsterpil k+1$
$2^{k}<n$

Andra algoritmer

Anteckningar

↑ 1 2 3 Richard P. Brent och Paul Zimmermann, Modern datoraritmetik
↑ Donald E. Knuth "Konsten att programmera", avsnitt 4.3.1
↑ Donald E. Knuth "Konsten att programmera", avsnitt 4.3.3, del A
↑ Rapporter från USSRs vetenskapsakademi 150 (1963), 496-498
↑ Toom 4-vägs multiplikation - GNU MP 5.1.3 . Hämtad 13 december 2013. Arkiverad från originalet 14 mars 2013. (obestämd)
↑ Donald E. Knuth "Konsten att programmera", avsnitt 4.3.3, del C
↑ Paul Zimmermann. Karatsuba kvadratrot. [Forskningsrapport] RR-3805, 1999, s.8. < inria-00072854 Arkiverad 2 december 2014 på Wayback Machine >
↑ Donald E. Knuth "Konsten att programmera datorer", volym 2, avsnitt 4.4
↑ Donald E. Knuth "Konsten att programmera datorer", volym 2, avsnitt 4.3.3

Litteratur

Donald E. Knuth, " The Art of Computer Programming ", volym 2, "Seminumerical Algorithms", 3:e upplagan, Addison-Wesley, 1998
Dan Zuras, "On Squaring and Multiplying Large Integers", ARITH-11: IEEE Symposium on Computer Arithmetic, 1993, s. 260 till 271.
DAN SSSR 150 (1963), 496-498
Richard P. Brent och Paul Zimmermann, Modern datoraritmetik
Elektroniska medel och kontrollsystem: Proceedings of the reports of the International Scientific and Practical Conference (13-16 oktober 2010). - Tomsk: V-Spectrum, 2011: Vid 2 timmar - Del 2. - 178 sid. ISBN 978-5-91191-223-6 , s.123-129

Datatyper
Otolkbart	Bit Knapra Byte qubit Behandla Drag Ord
Numerisk	Hela fixpunkt flytpunkt Rationell Komplex Lång intervall
Text	Symbolisk Sträng
Referens	Adress Länk Pekare Omslag
Sammansatt	Algebraisk datatyp ( generisk ) Klass Typ-produkt ( Skriv Tuple struktur ) Ett objekt Konsolidering ( taggat ) Beställt par
abstrakt	array Lista Sväng Stack Associativ array (visning, karta ) Mycket av multiset Typ Graf
Övrig	Logisk Lägre Högre Polymorf Funktionell uppräknad Samling Undantag Genus ( metaklass ) Monad Semafor Flöde tomhet
Relaterade ämnen	Abstrakt datatyp primitiv typ Datastruktur Generisk typ variabel Gränssnitt Konstruktör (OOP) Konstruktör (FP) Typ konstruktör Typ gjutning Prototyp Typ system