Dlouhá aritmetika

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 21. ledna 2022; kontroly vyžadují 2 úpravy .

Dlouhé aritmeticko - aritmetické operace prováděné pomocí počítače ( sčítání , odčítání , násobení , dělení , umocňování , elementární funkce ) na číslech, jejichž bitová hloubka přesahuje délku strojového slova tohoto počítače. Tyto operace jsou realizovány nikoli hardwarově, ale softwarově, s využitím základního hardwaru pro práci s čísly nižších řádů. Speciální případ - aritmetika s libovolnou přesností - se týká aritmetiky, ve které je délka čísel omezena pouze velikostí dostupné paměti.

Aplikace

Dlouhá aritmetika se používá v následujících oblastech:

kompilace kódu pro procesory ( mikrokontroléry ) s nízkou kapacitou . Například mikrokontroléry řady AVR mají 10bitový ADC a 8bitové registry . To nestačí ke zpracování informací z ADC; dlouhá aritmetika je nezbytná;
kryptografie . Většina systémů pro podepisování a šifrování dat používá celočíselnou aritmetiku modulo m, kde m je velmi velké přirozené číslo, které nemusí být nutně prvočíslo . Například při implementaci šifrovací metody RSA , Rabinova kryptosystému nebo schématu ElGamal je nutné zajistit přesnost výsledků násobení a umocňování v řádu 10 309 ;
matematický (viz seznam softwaru ) a finanční software . Výsledek výpočtu na papíře se musí do poslední číslice shodovat s výsledkem počítače. Zejména kalkulačka Windows (od Windows 95 ) provádí čtyři aritmetické operace s mnohem větší přesností, než umožňuje procesor x86 . Pro vědecké a technické výpočty se dlouhá aritmetika používá zřídka, protože chyby ve vstupních datech jsou obvykle mnohem větší než chyby zaokrouhlování;
standardní téma ve sportovním programování .

Požadovaný hardware pro práci s dlouhou aritmetikou

Přísně vzato, k implementaci aritmetiky s libovolnou přesností je od procesoru vyžadováno pouze nepřímé adresování ; v aritmetice s pevnou přesností se dokonce obejdete i bez ní. Některé funkce procesoru však zrychlují dlouhou aritmetiku a zároveň zjednodušují jeho programování.

Nosit vlajku . Operace "přidat / odečíst s přenosem", " otočit přes bit přenosu ".
Nepřímé adresování s auto-inkrementací a auto-dekrementací (indexový registr je po operaci inkrementován nebo dekrementován).
Násobení w · w = 2 w ( násobení slovo od slova, výsledkem je dvojslovo), dělení 2 w / w = w (s možným přetečením ).

Implementace v programovacích jazycích

Programovací jazyky mají vestavěné datové typy, které obecně nepřesahují 64 bitů (asi 10 19 ). Desítková dlouhá aritmetika byla implementována v sovětských programovacích jazycích ALMIR-65 na počítači MIR-1 a ANALYTIK na počítači MIR-2 . Pro práci s velkými čísly existuje v moderních programovacích jazycích poměrně málo hotových optimalizovaných knihoven pro dlouhou aritmetiku.

Většina funkčních jazyků vám umožňuje přepnout z běžné aritmetiky na dlouhou aritmetiku, aniž byste museli měnit aritmetický kód. Například Erlang a Scheme vždy představují přesná čísla stejně dlouhá. Ve Standard ML jsou implementace všech variant celých čísel určovány na základě signatury INTEGER, což vám umožňuje vybrat požadovanou dimenzi, včetně modulu IntInf, který implementuje celá čísla s libovolnou přesností; implementace PolyML tento modul standardně používá.

Existují vestavěné knihovny pro práci s velkými čísly v PascalABC.NET, Ruby , Python a Java .

Algoritmy

Násobící algoritmy

Následující reprezentace celých čísel se obvykle používá k popisu algoritmů. Je vybrána základna . Celé číslo délky pak může být reprezentováno jako [1] : $\beta >1$ $n$

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

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

Základní

Jde o algoritmus podle školní metody "ve sloupci". Chce to čas , kde jsou velikosti násobených čísel. $O(n\cdot m),$ $n,m$

Algoritmus může být reprezentován jako [1] [2] :

Algoritmus 1 BasecaseMultiply
Input: Output: for from to do $A=\součet \nolimits _{{i=0}}^{{m-1}}a_{i}\beta ^{i},B=\součet \nolimits _{{j=0}}^{{ n-1}}b_{j}\beta ^{j}$
$C=AB:=\součet \nolimits _{{k=0}}^{{m+n-1}}c_{k}\beta ^{k}$
$1:C\gets A\cdot b_{0}$
$2:$ $j$ $jeden$ $n-1$
$3:~~~~C\gets C+\beta ^{j}(A\cdot b_{j})$
$4:zpět~~C.$

Násobení Karatsuba

Karatsubova metoda násobení patří do paradigmatu „ rozděl a panuj “. Výpočetní složitost algoritmu:

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

Tento algoritmus je jednoduchou implementací [3] myšlenky rozdělení vstupních dat, která se stala základem pro algoritmy uvedené níže. Cílem je rozdělit jednu operaci násobení na -ciferných číslech na tři operace násobení na číslech délky plus [1] . $n$ $n/2$ $Na)$

K vynásobení dvou čísel větších než je strojové slovo se Karatsubův algoritmus volá rekurzivně, dokud nejsou čísla dostatečně malá, aby je bylo možné přímo násobit. Příklad takového algoritmu:

Algoritmus 2 KaratsubaMultiply
Vstup: Výstup: KaratsubaMultiply KaratsubaMultiply KaratsubaMultiply $A=\součet \nolimits _{{i=0}}^{{n-1}}a_{i}\beta ^{i},B=\součet \nolimits _{{j=0}}^{{ n-1}}b_{j}\beta ^{j}$
$C=AB:=\sum \nolimits _{{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}\gets sign(A_{0}-A_{1}),s_{B}\gets sign(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}}$

Pojďme počítat : $x=12345\cdot 6789$

12345=12\cdot 1000+345

6789=6\cdot 1000+789

Je třeba vypočítat tři mezilehlé koeficienty:

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

Výsledek:

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

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

Toomův algoritmus

Tento algoritmus je zobecněním algoritmu Karatsuba a je rychlejší. Jsou-li dána dvě celá čísla a , Toomův algoritmus je rozdělí na menší části, z nichž každá je rovna délce strojového slova, a provádí s těmito částmi operace. Výpočetní složitost algoritmu: $A$ $B$ $k$ $O(n^{\ln(2k-1)/\ln(k)}).$

Algoritmus Tooma-3

Myšlenku poprvé navrhl A. L. Toom v roce 1963 [4] , spočívá v rozdělení vstupních dat (násobičů) na 3 stejné části (pro zjednodušení jsou všechny části považovány za stejné). Toom-3 snižuje počet základních operací násobení z 9 na 5. Složitost algoritmu $O(n^{1,465}).$

Zvažte tento algoritmus v následujícím příkladu. Nechť jsou dvě čísla a . Nechť jsou operace definovány na číslech, jejichž velikost je rovna 1/3 velikosti původních čísel (viz obrázek). Předpokládáme také, že čísla zabírají stejnou paměť a jsou dělitelná přesně na 3 části, jinak obě čísla doplníme nulami na požadovanou velikost. $Y$ $X$

Poté dochází k zobrazení (parametrizaci) těchto částí na polynomy 2. stupně.

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

Uveďme podle definice takové, že hodnoty polynomů jsou rovny vstupním číslům a . Pro bitovou reprezentaci čísel je toto číslo dvě na mocninu rovnající se délce každé části v bitech. $b$ $X(b),~Y(b)$ $X$ $y$

Zavedeme také polynom:

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

(jeden)

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

Poté, co jsou prvky určeny - koeficienty polynomu , budou použity k získání , protože . Velikost koeficientů je 2krát větší (z paměti) než oddíl nebo . Konečné číslo rovnající se součinu lze nalézt sečtením s posunem, jak je znázorněno na obrázku níže. $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}$

Koeficienty lze vypočítat následovně: a tak dále, ale to bude vyžadovat všech 9 násobení: pro i je j=0,1,2 a bude ekvivalentní jednoduchému násobení. $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}$

Místo toho byl zvolen jiný přístup. se počítají v (1) na 5 bodech pro různé . $X(t),Y(t)$ $t$

Níže uvedená tabulka ukazuje hodnoty polynomů v rovnici (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}$

Parametr je podmíněný. Znamená to banální rovnost koeficientů na , takže hodnotu dostaneme okamžitě. Tento systém je lineární v 5 neznámých. Když se to vyřeší, dostaneme neznámé . Dále získáme hodnotu polynomu, jak je popsáno výše. $t=\infty$ $t^{4}$ $w_{4}$ $w_{i}$

Algoritmus Tooma-4

Složitost algoritmu Představuje 7 základních operací násobení. Toom-4 rozdělí vstup na 4 části. $O(n^{1.404}).$

Na stejném principu jako v Toom-3 sestavíme dva polynomy:

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)$ a jsou počítány v 7 různých bodech, počítá se také hodnota v těchto bodech. $Y(t)$ $W(t)$

$t=0$	$x_{0}\cdot y_{0},$ odkud se hned dostaneme $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},$ odkud se hned dostaneme $w_{6}$

Počet operací sčítání a násobení pro Toom-4 je mnohem větší než pro Toom-3. Některé výrazy se ale vyskytují více než jednou. Například počítáno pro a pro [5] . $x_{2}+x_{0}$ $t = 1$ $t = -1$

Toomův algoritmus pro libovolný oddíl

Toomův algoritmus pro dělení vstupních čísel na n operandů je ekvivalentní výše popsanému. Obecně platí, že rozdělení dvou stejně dlouhých operandů na části vede k výpočtu hodnot bodů . Jako body za vyřešení systému většinou berou . $r$ $2r-1$ $0,\infty ,+1,-1,\pm 2^{i},\pm 2^{{-i}}$

Fourierovo násobení

Tento násobící algoritmus se používá pro velká a velmi velká čísla [6] .

Tento algoritmus násobí dvě čísla v čase , kde je počet platných číslic ve vynásobených číslech (za předpokladu, že jsou stejná). Vytvoření je připisováno Cooley (Coolet) a Tyuki (Tukey) - 1965. Existují také návrhy, že tento algoritmus byl znám již dříve, ale neměl velký význam před vynalezením prvních počítačů. Pravděpodobní kandidáti na autorství vynálezu tohoto algoritmu se také nazývají Runge (Runge) a Koenig (Konig) - 1924, stejně jako Gauss - 1805. $O(n\cdot \log n),$ $n$

Nechť existuje číslo, znázorníme ho jako polynom, jak jsme to udělali dříve. Nazvěme tento polynom Také zavedeme diskrétní Fourierovu transformaci polynomu jako vektor se souřadnicemi . Kde jsou definovány jako - komplexní odmocnina tého stupně z 1, nerovná se 1. Faktem je, že komplexní odmocnina z 1 je definována až do fázového faktoru, počet těchto kořenů je . Fourierova transformace je použita za účelem nahrazení konvoluce koeficientů polynomů a : - součinem jejich Fourierových obrazů. $A(x).$ $\left(b_{1},b_{2},b_{3},b_{4},\tečky 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)),

kde násobení znamená skalární součin vektorů. $F(A)\cdot F(B)$

Předpokládejme, že existuje mocnina dvou. $n$

Hledání se provádí rekurzivně (rozděl a panuj). Cílem je rozdělit původní polynom na dva polynomy, $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}+\tečky +a_{{n-2}}x_{{{\frac { n-2}{2}}}}

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

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

Všimněte si, že ze všech čísel jsou pouze různá. Proto bude DFT -element . A protože DFT se skládá z prvků, pak komplexní kořen 1 bude kořenem stupně . $\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))$

Prostředek,

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

kde a $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}}).

Použili jsme vlastnosti komplexních čísel: různé kořeny stupně všeho . . $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}$

Získáme rekurzivní algoritmus:
DFT jednoho prvku se rovná tomuto prvku
, abychom našli DFT A, rozdělíme koeficienty A na sudé a liché, dostaneme dva polynomy a , najdeme pro ně DFT, najdeme DFT : pro . Existuje důkaz následujícího tvrzení: Inverzní DFT se nalézá podobně jako přímá DFT s tím rozdílem, že body jsou brány jako body, které jsou symetrické podle skutečné osy, místo těch, které se používají v přímé transformaci DFT. Je také nutné vydělit všechny koeficienty polynomu 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$

Algoritmy extrakce kořenů

Druhá odmocnina

Jedním z algoritmů druhé odmocniny je algoritmus Karatsuba Square Root. Toto je zdaleka nejznámější metoda pro výpočet druhé odmocniny n - ciferného čísla. Tento algoritmus využívá rychlou Fourierovu transformaci a Newtonovu metodu se složitostí 5 M ( n ) [7] .

Prezentovaný algoritmus je založen na dělení Burnickel-Ziegler (Burnikel-Ziegler) Karatsuba. Vzhledem k celému číslu n algoritmus vypočítá současně jeho celočíselnou odmocninu a odpovídající zbytek, což je Toto není asymptoticky optimální, ale v praxi velmi efektivní s řádovou složitostí operací, kde K ( n ) je počet operací potřebných k vynásobení dvě n - bitová čísla pomocí algoritmu Karatsuba. Důvodem této nízké složitosti je krásná divize Karatsuba, kterou nedávno objevili Burnickel a Ziegler, a pečlivé zacházení se zbytky, které se vyhýbá zbytečným výpočtům. $s=\lfloor {\sqrt {n}}\rfloor$ $r=ns^{2}.$ ${\frac {3}{2}}K(n)$

Věta . Počet operací, které používá algoritmus SqrtRem s 2n - bitovým vstupem, je omezený

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

kde K ( n ) je počet operací potřebných k vynásobení 2 n -bitových čísel pomocí Karatsubova algoritmu.

Algoritmus SqrtRem Vstup: s výstupem: takový, že pokud se vrátí

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

Algoritmy pro převod číselné soustavy

Předpokládejme, že převádíte ze základu b na základ B [8] .

Způsoby převodu celých čísel

Metoda 1 (Dělení B pomocí reprezentace čísel se základem b). Pro dané celé číslo u lze
získat reprezentaci ve formátu základního B formuláře , tím, že uděláme ${\displaystyle (\dots U_{2}U_{1}U_{0})_{B))$

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

, , , do .

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

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

\left\lfloor \dots {\left\lpatro {\left\lfloor {\frac {u}{B))\right\rfloor }\right\rfloor }{\tečky /B}\right\rfloor = 0

Metoda 2 (Násobení B pomocí reprezentace báze b). Pokud má reprezentace čísla u v základu b tvar , pak pomocí aritmetických operací s čísly, která jsou reprezentována ve formátu v základu B, můžete získat polynom ve tvaru (( . ${\displaystyle (u_{m}\tečky 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))$

Metoda 1 (a) (Násobení b pomocí základní B reprezentace čísel). Pro dané zlomkové číslo a můžete vypočítat hodnoty číslic jeho reprezentace v základu B takto: , , ,… kde {x} znamená xmod1 = x- . Pro zaokrouhlení výsledku na M číslic lze výpočet po obdržení přerušit , a pokud je {…{{uВ}В}...В} větší než 1/2, pak by se hodnota měla zvýšit o jednu. (Upozorňujeme však, že tato operace může vést k nutnosti provádět překlady, které by měly být zahrnuty do výsledku pomocí aritmetických operací v základu B. Před zahájením výpočtů by bylo jednodušší přidat k původnímu číslu u konstantu , ale to může vést k nesprávnému výsledku, pokud v počítači nelze číslo přesně vyjádřit ve formátu základu b. Všimněte si také, že je možné zaokrouhlit výsledek na if ). Metoda 2 (a) (Násobení B pomocí reprezentace báze b). Pokud má reprezentace čísla a v základu b tvar , pak pomocí aritmetických operací s čísly, která jsou uvedena ve formátu v základu B, můžete získat polynom ve tvaru ((… + …) + . $(.U_{{-1}}U_{{-2}}...)_{{B}}$
$U_{{-1}}=\levá\lpatro \ {uB}\pravá\rpatro$ $U_{{-2}}{=}\levá\lpatro \ {{uB}B}\pravá\rpatro$ $U_{{-3}}=\levá\lpatro \ {((uB)B)B}\pravá\rpatro$ $\left\lfloor \{x}\right\rpatro$ $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}}$

Způsoby převodu zlomkových čísel

Metoda 1 (b) (Násobení b pomocí základní B reprezentace čísel). Pro dané zlomkové číslo u můžete vypočítat hodnoty bitů jeho reprezentace v základu B takto: , , ,… kde {x} znamená xmod1 = x- . Pro zaokrouhlení výsledku na M číslic lze výpočet po obdržení přerušit , a pokud je {…{{uВ}В}...В} větší než 1/2, pak by se hodnota měla zvýšit o jednu. (Upozorňujeme však, že tato operace může vést k nutnosti provádět překlady, které by měly být zahrnuty do výsledku pomocí aritmetických operací v základu B. Před zahájením výpočtů by bylo jednodušší přidat k původnímu číslu u konstantu , ale to může vést k nesprávnému výsledku, pokud v počítači nelze číslo přesně vyjádřit ve formátu základu b. Všimněte si také, že je možné zaokrouhlit výsledek na if ). $(0.U_{{-1}}U_{{-2}}...)_{{B}}$
$U_{{-1}}=\levá\lpatro \ {uB}\pravá\rpatro$ $U_{{-2}}{=}\levá\lpatro \ {{uB}B}\pravá\rpatro$ $U_{{-3}}=\levá\lpatro \ {((uB)B)B}\pravá\rpatro$ $\left\lfloor \{x}\right\rpatro$ $U_{{M}}$ $U_{{M}}$ $1/2B^{{-M}}$ $1/2B^{{-M}}$ $(1,00...0)^{B}$ $b^{{m}}$ $\geq$ $2B^{{M}}$

Metoda 2 (b) (Dělení b pomocí reprezentace čísel na bázi B). Pokud je číslo u reprezentováno v základu b jako , pak pomocí aritmetických operací v základu B lze vypočítat jako . Je nutné pečlivě sledovat chyby, ke kterým dochází při ořezávání nebo zaokrouhlování při operaci dělení b; jsou obvykle bezvýznamné, ale není tomu tak vždy. $(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$

Vícenásobná přesná transformace

Nejpohodlnější je začít s převodem velmi dlouhých čísel převodem bloků bitů, s nimiž lze operace provádět s jedinou přesností. Tyto bloky pak zkombinujete pomocí jednoduchých metod, které jsou specifické pro vícenásobnou přesnost. Například nechť 10n je nejvyšší mocnina o 10 menší než velikost strojového slova. Potom:
a) pro převod celého čísla "Číslo s násobnou přesností z binárního na desítkové je nutné jej vynásobit 10n (tedy převést z binárního na desítkové se základem 10n metodou 1, a); pomocí operací s jedinou přesností, získáme n desetinných míst pro každou reprezentační jednotku v základu 10n;
b) pro převod zlomkové části „Část čísla s vícenásobnou přesností z binárního na desetinné postupujte obdobným způsobem vynásobením : (tj. pomocí metody 2, a, kde B \u003d 10n); c) pro převod celého čísla s násobnou přesností z desítkové na binární nejprve převedeme bloky o n bitech; potom pro převod ze základu 10n na binární použijte metodu 1, b; d) Chcete-li převést zlomkovou část s vícenásobnou přesností z desítkové na binární, nejprve převeďte na základ 10n jako v postupu (c) a poté použijte metodu 2, b. $10^{n}$

Algoritmy dělení

Výsledkem algoritmu pro dělení n-bitového čísla u n-bitovým číslem v musí být dvě n-bitová čísla - u mod v a u div v. Algoritmy popsané níže nejsou v praxi použitelné, protože jako výsledek dělení naleznou reálné číslo a ne dvě n-bitová čísla.

Teoreticky, pro dělení n-bitového čísla u n-bitovým číslem v, můžete nejprve najít n-bitovou aproximaci k číslu 1/v, pak ji vynásobit u, čímž získáte aproximaci k , a nakonec proveďte další násobení, abyste provedli malou opravu, abyste se ujistili, že nerovnost platí . Na základě výše uvedeného stačí mít účinný algoritmus, který by z daného n-bitového čísla vytvořil přibližnou hodnotu čísla, které je inverzní k n-bitovému číslu. Dále použijte algoritmus pro násobení n-bitových čísel. [9] ${\klobouk {q}}$ $u/v$ ${\klobouk {q}}$ $0\leq u-qv<v$

Algoritmus R (Získání reciproční hodnoty s vysokou přesností) Nechť číslo v má binární reprezentaci , kde . Tento algoritmus vypočítá aproximaci z čísla tak, že . R1 (počáteční odhad) Přiřadit a . R2 (Newton Iteration) Zde máme číslo z v binárním tvaru se znaménky za dělicím bodem a . Počítejte přesně pomocí programu rychlého násobení . Poté spočítejte kde přesně . Pak přiřaďte , kde , která vyhovuje nerovnosti , se podle potřeby přidá k zaokrouhlení tak , aby byl násobkem . A nakonec přiřadit . R3 If , pak se vraťte ke kroku R2; jinak se provádění algoritmu ukončí. $v=(0.v_{{1}}v_{{2}}v_{{3}})_{{2}}$ $v_{{1}}=1$ $1/obj$
$|z-1/v|\leq 2^{{-n}}$
$z\leftarrow {\frac {1}{4}}\left\lpatro {\frac {32}{(4v_{{1}}+2v_{{2}}+v_{{3}})))}\ pravé \rpatro$ $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$

Jiné algoritmy

Poznámky

↑ 1 2 3 Richard P. Brent a Paul Zimmermann, Moderní počítačová aritmetika
↑ Donald E. Knuth „Umění počítačového programování“, oddíl 4.3.1
↑ Donald E. Knuth „Umění počítačového programování“, oddíl 4.3.3, část A
↑ Zprávy Akademie věd SSSR 150 (1963), 496-498
↑ Toom 4-cestné násobení - GNU MP 5.1.3 . Získáno 13. prosince 2013. Archivováno z originálu dne 14. března 2013. (neurčitý)
↑ Donald E. Knuth „Umění počítačového programování“, oddíl 4.3.3, část C
↑ Paul Zimmermann. Karatsuba druhá odmocnina. [Výzkumná zpráva] RR-3805, 1999, s.8. < inria-00072854 Archivováno 2. prosince 2014 na Wayback Machine >
↑ Donald E. Knuth „Umění počítačového programování“, svazek 2, oddíl 4.4
↑ Donald E. Knuth „Umění počítačového programování“, svazek 2, oddíl 4.3.3

Literatura

Donald E. Knuth, " The Art of Computer Programming ", svazek 2, "Seminumerical Algorithms", 3. vydání, Addison-Wesley, 1998
Dan Zuras, "On Squaring and Multiplying Large Integers", ARITH-11: IEEE Symposium on Computer Arithmetic, 1993, str. 260 až 271.
DAN SSSR 150 (1963), 496-498
Richard P. Brent a Paul Zimmermann, Moderní počítačová aritmetika
Elektronické prostředky a řídicí systémy: Sborník zpráv z Mezinárodní vědecko-praktické konference (13.-16. října 2010). - Tomsk: V-Spectrum, 2011: Ve 2 hodiny - Část 2. - 178 s. ISBN 978-5-91191-223-6 , s.123-129

Typy dat
Neinterpretovatelné	Bit Okusovat Byte qubit Zacházet Vlastnost Slovo
Numerický	Celý pevný bod plovoucí bod Racionální Komplex Dlouho časový úsek
Text	Symbolický Tětiva
Odkaz	Adresa Odkaz Ukazatel Obal
Kompozitní	Algebraický datový typ ( generický ) Třída Typový produkt ( Write Tuple struktura ) Objekt Konsolidace ( označeno ) Objednaný pár
abstraktní	pole Seznam Otočit se Zásobník Asociativní pole (displej, mapa ) Hodně multiset Typ Graf
jiný	Logický Dolní Vyšší Polymorfní Funkční spočítatelný Sbírka Výjimka Rod ( metatřída ) Monad Semafor Tok prázdnota
související témata	Abstraktní datový typ primitivní typ Datová struktura Obecný typ proměnné Rozhraní Konstruktor (OOP) konstruktér (FP) Typový konstruktor Typové odlévání Prototyp Typový systém