Hosszú aritmetika

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. január 21-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

Hosszú aritmetikai - Számítógéppel végrehajtott aritmetikai műveletek ( összeadás , kivonás , szorzás , osztás , hatványozás , elemi függvények ) olyan számokon, amelyek bitmélysége meghaladja a számítógép gépi szavának hosszát . Ezeket a műveleteket nem hardverben, hanem szoftverben valósítják meg, az alapvető hardvert felhasználva, hogy kisebb számú megrendeléssel dolgozhassanak. Egy speciális eset - tetszőleges precíziós aritmetika - olyan aritmetikára vonatkozik, amelyben a számok hosszát csak a rendelkezésre álló memória mennyisége korlátozza.

Alkalmazás

A hosszú aritmetika a következő területeken használatos:

kód összeállítása kis kapacitású processzorokhoz ( mikrokontrollerekhez ) . Például az AVR sorozatú mikrokontrollerek 10 bites ADC - vel és 8 bites regiszterekkel rendelkeznek . Ez nem elég az ADC-től származó információk feldolgozásához; a hosszú aritmetika nélkülözhetetlen;
kriptográfia . A legtöbb adataláíró és titkosító rendszer egész szám aritmetikai modulo m-t használ, ahol m egy nagyon nagy természetes szám, nem feltétlenül prím . Például az RSA titkosítási módszer , a Rabin titkosítási rendszer vagy az ElGamal séma alkalmazásakor biztosítani kell a 10 309 -es nagyságrendű szorzás és hatványozás eredményeinek pontosságát ;
matematikai (lásd a szoftverek listáját ) és pénzügyi szoftvereket . A papíron végzett számítás eredményének meg kell egyeznie a számítógép eredményével az utolsó számjegyig. Különösen a Windows számológép (a Windows 95 óta ) négy aritmetikai műveletet hajt végre sokkal nagyobb pontossággal, mint amit az x86 processzor lehetővé tesz . Tudományos és mérnöki számításokhoz ritkán használnak hosszú aritmetikát, mivel a bemeneti adatok hibái általában sokkal nagyobbak, mint a kerekítési hibák;
standard téma a sportprogramozásban .

Szükséges hardver a hosszú aritmetikához

Szigorúan véve csak közvetett címzés szükséges a processzortól az önkényes pontosságú aritmetika megvalósításához ; fix pontosságú aritmetikában akár nélküle is megteheti. Bizonyos processzorfunkciók azonban felgyorsítják a hosszú aritmetikát, miközben leegyszerűsítik a programozást.

Hordj zászlót . Műveletek "összeadás / kivonás átvitellel", " forgatás a hordozóbiten keresztül ".
Közvetett címzés automatikus növeléssel és automatikus csökkentéssel (az indexregiszter a művelet után növekszik vagy csökken).
Szorzás w · w = 2 w ( szóról szóra szorzás, az eredmény dupla szó), 2 osztás w / w = w (esetleges túlcsordulással ).

Megvalósítás programozási nyelveken

A programozási nyelvek beépített adattípusokkal rendelkeznek, amelyek általában nem haladják meg a 64 bitet (körülbelül 10 19 ). A tizedesjegyű hosszú aritmetika a szovjet ALMIR-65 programozási nyelveken valósult meg a MIR-1 számítógépen és az ANALYTIK a MIR-2 számítógépen . A nagy számokkal való munkavégzéshez a modern programozási nyelvekben jó néhány kész optimalizált könyvtár található a hosszú aritmetika számára.

A legtöbb funkcionális nyelv lehetővé teszi, hogy a normál aritmetikáról a hosszú aritmetikára váltson anélkül, hogy meg kellene változtatnia az aritmetikai kódot. Például az Erlang és a Scheme mindig pontos számokat jelent, amíg hosszú. A Standard ML -ben az egész számok összes változatának megvalósítását az aláírás alapján határozzák meg INTEGER, lehetővé téve a kívánt dimenzió kiválasztását, beleértve egy olyan modult is IntInf, amely tetszőleges pontosságú egész számokat valósít meg; a PolyML implementáció alapértelmezés szerint ezt a modult használja.

A PascalABC.NET, a Ruby , a Python és a Java beépített könyvtárai nagy számokkal dolgozhatnak .

Algoritmusok

Szorzóalgoritmusok

Az egész számok alábbi ábrázolását általában az algoritmusok leírására használják. Az alap ki van választva . Ekkor a hosszúságú egész szám a következőképpen ábrázolható: [1] : $\beta >1$ $n$

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

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

Alap

Ez egy iskolai módszer szerinti algoritmus "oszlopban". Időbe telik, hol vannak a szorzott számok mérete. $O(n\cdot m),$ $n,m$

Az algoritmus a következőképpen ábrázolható: [1] [2] :

1. algoritmus BasecaseMultiply
Input: Output: for from to do $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\get A\cdot b_{0}$
$2:$ $j$ $egy$ $n-1$
$3:~~~~C\get C+\beta ^{j}(A\cdot b_{j})$
$4:visszatérés~~C.$

Karatsuba szorzása

A Karatsuba szorzási módszere az „ oszd meg és uralkodj ” paradigmához tartozik. Az algoritmus számítási összetettsége :

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

Ez az algoritmus a bemeneti adatok felosztásának ötletének egyszerű megvalósítása [3] , amely az alább felsorolt algoritmusok alapja lett. Az ötlet az, hogy egy számjegyű számok szorzási műveletét három szorzási műveletre osztják fel olyan számokkal, amelyek hosszúsága plusz [1] . $n$ $n/2$ $Tovább)$

Két, egy gépi szónál nagyobb szám szorzásához a Karatsuba algoritmusát rekurzív módon hívják meg, amíg a számok elég kicsik lesznek ahhoz, hogy közvetlenül megszorozzák. Példa egy ilyen algoritmusra:

2. algoritmus KaratsubaMultiply
Bemenet: Kimenet: 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\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}}$

Számoljunk : $x=12345\cdot 6789$

12345=12\cdot 1000+345

6789=6\cdot 1000+789

Három köztes együtthatót kell kiszámítani:

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

Eredmény:

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

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

Tooma algoritmusa

Ez az algoritmus a Karatsuba algoritmus általánosítása és gyorsabb. Adott két egész szám és , a Toom-algoritmus kisebb részekre osztja őket , amelyek mindegyike megegyezik egy gépszó hosszával, és ezeken a részeken műveleteket hajt végre. Az algoritmus számítási összetettsége: $A$ $B$ $k$ $O(n^{\ln(2k-1)/\ln(k)}).$

Tooma-3 algoritmus

Az ötletet először A. L. Toom vetette fel 1963-ban [4] , és a bemeneti adatok (szorzók) 3 egyenlő részre osztásából áll (az egyszerűség kedvéért minden részt egyenlőnek tekintünk). A Toom-3 9-ről 5-re csökkenti az elemi szorzási műveletek számát. Algoritmus bonyolultsága $O(n^{1,465}).$

Tekintsük ezt az algoritmust a következő példában. Legyen két szám és . Legyenek műveletek olyan számokra, amelyek mérete megegyezik az eredeti számok méretének 1/3-ával (lásd az ábrát). Azt is feltételezzük, hogy a számok egyenlő memóriát foglalnak el, és pontosan 3 résszel oszthatók, ellenkező esetben mindkét számot nullákkal töltjük fel a kívánt méretre. $Y$ $x$

Ezután következik ezen részek leképezése (parametrizálása) a 2. fokú polinomokra.

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

Vezessünk be definíció szerint olyat, hogy a polinomok értéke rendre egyenlő legyen a bemeneti számokkal és . A számok bitenkénti ábrázolása esetén ez a szám kettő az egyes részek bitben kifejezett hosszának hatványa. $b$ $X(b),~Y(b)$ $x$ $y$

Bevezetünk egy polinomot is:

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

(egy)

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

Miután meghatároztuk az elemeket - a polinom együtthatóit , akkor azokat felhasználjuk annak érdekében, hogy megkapjuk , mivel . Az együtthatók mérete 2-szer nagyobb (memóriából), mint a partíció vagy . A termékkel megegyező végső számot eltolással összeadva találhatjuk meg , ahogy az alábbi ábrán látható. $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}$

Az együtthatók a következőképpen számíthatók ki: és így tovább, de ehhez mind a 9 szorzásra lesz szükség: i esetén j=0,1,2, és egy egyszerű szorzással ekvivalens lesz. $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}$

Ehelyett más megközelítést alkalmaztak. az (1)-ben 5 pontban vannak kiszámítva különböző . $X(t),Y(t)$ $t$

Az alábbi táblázat az (1) egyenletben szereplő polinomok értékeit mutatja.

$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)~~~=~16h_{4}+8h_{3}+4h_{2}+2h_{1}+sz_{0}$
$t=\infty$	$x_{2}\cdot y_{2}$	$W(\infty )~~=~~~~w_{4}$

A paraméter feltételes. Ez az együtthatók banális egyenlőségét jelenti -nél , így azonnal megkapjuk az értéket . Ez a rendszer 5 ismeretlenben lineáris. Amikor megoldódik, ismeretleneket kapunk . Ezután megkapjuk a polinom értékét a fent leírtak szerint. $t=\infty$ $t^{4}$ $w_{4}$ $w_{i}$

Tooma-4 algoritmus

Az algoritmus összetettsége 7 elemi szorzási műveletet reprezentál. A Toom-4 a bemenetet 4 részre osztja. $O(n^{1,404}).$

Ugyanazzal az elvvel, mint a Toom-3-ban, két polinomot építünk:

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

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

$X(t)$ és 7 különböző ponton számítják ki, az ezeken a pontokon lévő értékeket is kiszámítja. $I(t)$ $W(t)$

$t=0$	$x_{0}\cdot y_{0},$ ahonnan azonnal eljutunk $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},$ ahonnan azonnal eljutunk $w_{6}$

Az összeadási és szorzási műveletek száma a Toom-4 esetében sokkal nagyobb, mint a Toom-3 esetében. De néhány kifejezés többször előfordul. Például az [5] -re és a következőre számítva . $x_{2}+x_{0}$ $t=1$ $t=-1$

Toom algoritmusa tetszőleges partícióhoz

Toom algoritmusa, amely a bemeneti számokat n operandusra osztja, megegyezik a fent leírt algoritmussal. Általában két egyforma hosszú operandus részekre osztása pontértékek kiszámítását eredményezi . A rendszer megoldásának pontjaként általában . $r$ $2r-1$ $0,\infty ,+1,-1,\pm 2^{i},\pm 2^{{-i}}$

Fourier-szorzás

Ezt a szorzási algoritmust nagy és nagyon nagy számokhoz használják [6] .

Ez az algoritmus időben megszoroz két számot, ahol a szorzott számok jelentős számjegyeinek száma (feltéve, hogy egyenlők). Az alkotás Cooley (Coolet) és Tyuki (Tukey) nevéhez fűződik – 1965. Arra is utalnak, hogy ez az algoritmus korábban is ismert volt, de nem volt nagy jelentősége az első számítógépek feltalálása előtt. Az algoritmus feltalálásának szerzőjének valószínű jelöltjei Runge (Runge) és Koenig (Konig) - 1924, valamint Gauss - 1805 is. $O(n\cdot \log n),$ $n$

Legyen szám, polinomként ábrázoljuk, ahogy korábban is tettük. Nevezzük ezt a polinomot Szintén bevezetjük a polinom diszkrét Fourier transzformációját, mint vektort , koordinátákkal . Ahol definíció szerint - az 1-edik fok komplex gyöke , amely nem egyenlő 1-gyel. Az a tény, hogy 1 komplex gyöke egy fázistényezőig van definiálva, ezeknek a gyökereknek a száma . A Fourier-transzformációt alkalmazzuk a polinomok együtthatóinak konvolúciójának helyettesítésére és : - Fourier-képeik szorzatára. $A(x).$ $\left(b_{1},b_{2},b_{3},b_{4},\dots b_{n-1}\right)$ $kettős]$ $w^{n}[én]$ $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)),

ahol a szorzás a vektorok skaláris szorzatát jelenti. $F(A)\cdot F(B)$

Tegyük fel, hogy van kettő hatványa. $n$

A keresés rekurzív módon történik (oszd meg és uralkodj). Az ötlet az, hogy az eredeti polinomot két polinomra osztjuk, $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}+\pontok +a_{{n-2}}x_{{{\frac { n-2}{2}}}}

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

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

Vegye figyelembe, hogy az összes szám közül csak különbözőek. Ezért a DFT -elem lesz . És mivel a DFT elemekből áll , akkor 1 komplex gyöke lesz a fok gyöke . $\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))$

Eszközök,

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

hol és $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}}).

A komplex számok tulajdonságait használtuk: minden fokának különböző gyökei . . $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}$

Kapunk egy rekurzív algoritmust: az
egyik elem DFT-je egyenlő ezzel az elemmel
, hogy megtaláljuk az A DFT-t, az A együtthatókat felosztjuk párosra és páratlanra, két polinomot kapunk , és megkeressük a DFT-t, megkeressük a DFT-t. : for . Bizonyíték van a következő állításra: Az inverz DFT-t a közvetlen DFT-hez hasonlóan találjuk meg, azzal a különbséggel, hogy a pontokat a valós tengelyre szimmetrikus pontoknak vesszük, nem pedig a közvetlen DFT-transzformációnál. Ezenkívül el kell osztani a polinom összes együtthatóját n-nel $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$

Gyökérkivonási algoritmusok

Négyzetgyök

Az egyik négyzetgyök algoritmus a Karatsuba négyzetgyök algoritmus. Ez messze a legismertebb módszer egy n - jegyű szám négyzetgyökének kiszámítására. Ez az algoritmus a gyors Fourier-transzformációt és a Newton-módszert használja 5 M ( n ) bonyolultsággal [7] .

A bemutatott algoritmus Burnickel-Ziegler (Burnikel-Ziegler) Karatsuba felosztásán alapul. Adott egy n egész szám , az algoritmus egyidejűleg kiszámítja egész négyzetgyökét és a megfelelő maradékot, ami a Ez nem aszimptotikusan optimális, de a gyakorlatban nagyon hatékony a műveleti sorrend bonyolultsága mellett, ahol K ( n ) a szorzáshoz szükséges műveletek száma. két n bites szám a Karatsuba algoritmus segítségével. Ennek az alacsony bonyolultságnak az oka a Burnickel és Ziegler által nemrégiben felfedezett gyönyörű Karatsuba részleg, valamint a maradékok gondos kezelése, amely elkerüli a felesleges számításokat. $s=\lfloor {\sqrt {n}}\rfloor$ $r=ns^{2}.$ ${\frac {3}{2}}K(n)$

Tétel . Az SqrtRem algoritmus által 2n bites bemenettel végzett műveletek száma korlátozott

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

ahol K ( n ) a 2 n bites szám megszorzásához szükséges műveletek száma Karatsuba algoritmusával.

Algoritmus SqrtRem Bemenet: kimenettel: olyan , hogy ha majd visszatér

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

0\leq a_{i}<b

a_{3}\geq b/4

{\megjelenítési stílus (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

{\megjelenítési stílus (s,r)}

Algoritmusok a számrendszer átalakításához

Tegyük fel, hogy b bázisból B bázisba konvertál [8] .

Egész számok konvertálásának módjai

1. módszer (Osztás B-vel a számok b bázisábrázolásával). Adott u egész számra
az alak B bázisformátumú reprezentációját kaphatjuk meg , ha ezt csináljuk ${\displaystyle (\dots U_{2}U_{1}U_{0})_{B))$

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

, , , óráig .

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

2. módszer (Szorzás B-vel a b bázisábrázolás használatával). Ha az u szám b bázisbeli reprezentációja formájú , akkor olyan számokkal végzett aritmetikai műveletekkel, amelyek a B bázis formátumában vannak ábrázolva, egy polinomot kaphatunk a ( ( . ${\displaystyle (u_{m}\pontok 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}+\pontok )b+u_{1}b+u_{0))$

1. módszer (a) (Szorzás b-vel a számok B alapú reprezentációjával). Egy adott törtszámhoz és a B bázisban lévő reprezentáció számjegyeinek értékét a következőképpen számíthatja ki: , , ,… ahol {x} jelentése xmod1 = x- . Az eredmény M számjegyre kerekítéséhez a számítás megszakítható a vétel után , és ha {…{{uВ}В}...В} nagyobb, mint 1/2, akkor az értéket növelni kell eggyel. (Megjegyzendő azonban, hogy ez a művelet fordítások végrehajtását vonhatja maga után, amelyeket a B bázis aritmetikai műveleteivel kell az eredményben szerepeltetni. A számítások megkezdése előtt egyszerűbb lenne egy konstanst hozzáadni az eredeti u számhoz , de ez hibás eredményhez vezethet, ha számítógépen a szám nem ábrázolható pontosan b alapformátumban. Vegye figyelembe azt is, hogy az eredmény kerekíthető ha -ra ). 2. módszer (a) (Szorzás B-vel a b bázis reprezentációjával). Ha egy szám ábrázolása b bázisban alakja , akkor a B bázis formátumában megjelenő számokkal végzett aritmetikai műveletek segítségével egy polinomot kaphatunk ((… + …) + alakban . $(.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}}$

A törtszámok átalakításának módjai

1. b) módszer (Szorzás b-vel a számok B alapú reprezentációjával). Egy adott u törtszámhoz a következőképpen számíthatja ki a reprezentációja bitjeinek értékét a B bázisban: , , ,… ahol {x} azt jelenti, hogy xmod1 = x- . Az eredmény M számjegyre kerekítéséhez a számítás megszakítható a vétel után , és ha {…{{uВ}В}...В} nagyobb, mint 1/2, akkor az értéket növelni kell eggyel. (Megjegyzendő azonban, hogy ez a művelet fordítások végrehajtását vonhatja maga után, amelyeket a B bázis aritmetikai műveleteivel kell az eredményben szerepeltetni. A számítások megkezdése előtt egyszerűbb lenne egy konstanst hozzáadni az eredeti u számhoz , de ez hibás eredményhez vezethet, ha számítógépen a szám nem ábrázolható pontosan b alapformátumban. Vegye figyelembe azt is, hogy az eredmény kerekíthető ha -ra ). $(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}}$

2. b) módszer (Osztás b-vel a számok B alapú reprezentációjával). Ha az u számot a b bázisban mint , akkor a B bázisban végrehajtott aritmetikai műveletek segítségével úgy számíthatjuk ki . Gondosan figyelemmel kell kísérni azokat a hibákat, amelyek a b-vel történő osztási művelet során csonkolva vagy kerekítve fordulnak elő; általában jelentéktelenek, de ez nem mindig van így. $(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$

Többszörös precíziós transzformáció

A legkényelmesebb a nagyon hosszú számok konvertálását bitblokkok átalakításával kezdeni, amelyeken a műveleteket egyetlen pontossággal lehet végrehajtani. Ezután kombinálja ezeket a blokkokat egyszerű módszerekkel, amelyek a többszörös pontosságra jellemzőek. Legyen például 10n a gépi szóméretnél kisebb 10-el kisebb hatvány. Ezután:
a) egy egész szám "szám többszörös pontosságú binárisról decimálisra konvertálásához meg kell szorozni 10n-nel (így binárisról decimálisra konvertálni 10n bázissal az 1. a módszerrel); egyetlen pontosságú műveletek segítségével, n tizedesjegyet kapunk minden egyes reprezentációs egységhez a 10n bázisban;
b) a többszörös pontosságú szám törtrészének binárisból decimálissá konvertálásához hasonló módon járjunk el úgy, hogy megszorozzuk a következővel: (azaz a 2. módszerrel, a, ahol B \u003d 10n); c) egy egész szám többszörös pontosságú decimálisról binárisra konvertálásához először n bites blokkokat konvertálunk; majd a 10n bázisból binárissá konvertálásához használja az 1. b módszert; d) Több pontosságú törtrész decimálisról binárisra konvertálásához először konvertálja át 10n bázisra a (c) eljárás szerint, majd használja a 2. b) módszert. $10^{n}$

Osztási algoritmusok

Az n bites u számot egy v n bites számmal osztó algoritmusnak két n bites számot kell eredményeznie - u mod v és u div v. Az alábbiakban ismertetett algoritmusok a gyakorlatban nem alkalmazhatók, mivel nem két n bites számot, hanem valós számot találnak az osztás eredményeként.

Elméletileg egy n-bites u szám elosztása egy n-bites v számmal, először találhat egy n-bites közelítést az 1/v számhoz, majd megszorozhatja u-val, ami közelítést ad a -hoz , és végül hajtson végre egy másik szorzást, hogy egy kis korrekciót végezzen, hogy megbizonyosodjon az egyenlőtlenség érvényéről . A fentiek alapján elegendő egy hatékony algoritmus, amely egy adott n bites számból egy n bites szám inverzének közelítő értékét képezné. Ezután alkalmazza az n bites számok szorzására szolgáló algoritmust. [9] ${\kalap {q}}$ $u/v$ ${\kalap {q}}$ $0\leq u-qv<v$

R algoritmus (A reciprok nagy pontosságú megszerzése) Legyen a v számnak bináris reprezentációja , ahol . Ez az algoritmus kiszámítja a szám z közelítését úgy, hogy . R1 (kezdeti tipp) Rendelje hozzá és . R2 (Newton-iteráció) Itt van a z szám bináris formában , az osztópont és az előjelekkel . Számítsa ki pontosan a gyorsszorzó programmal . Ezek után számold ki, hogy pontosan hol . Ezután rendelje hozzá , ahol , amely kielégíti az egyenlőtlenséget , szükség szerint hozzáadódik a kerekítéshez , hogy többszöröse legyen . És végül kiosztani . R3 Ha , akkor térjen vissza az R2 lépéshez; ellenkező esetben az algoritmus végrehajtása véget ér. $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}})))}\ jobb \rpadló$ $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$

Egyéb algoritmusok

Jegyzetek

↑ 1 2 3 Richard P. Brent és Paul Zimmermann, Modern számítógépes aritmetika
↑ Donald E. Knuth "A számítógépes programozás művészete", 4.3.1
↑ Donald E. Knuth "A számítógépes programozás művészete", 4.3.3. szakasz, A rész
↑ A Szovjetunió Tudományos Akadémia jelentései 150 (1963), 496-498
↑ Toom 4-utas szorzás - GNU MP 5.1.3 . Letöltve: 2013. december 13. Az eredetiből archiválva : 2013. március 14.. (határozatlan)
↑ Donald E. Knuth "A számítógépes programozás művészete", 4.3.3. szakasz, C rész
↑ Paul Zimmermann. Karatsuba négyzetgyökér. [Kutatási jelentés] RR-3805, 1999, 8. o. < inria-00072854 Archiválva : 2014. december 2. a Wayback Machine -nél >
↑ Donald E. Knuth "A számítógépes programozás művészete", 2. kötet, 4.4.
↑ Donald E. Knuth "A számítógépes programozás művészete", 2. kötet, 4.3.3.

Irodalom

Donald E. Knuth, " The Art of Computer Programming ", 2. kötet, "Seminumerical Algorithms", 3. kiadás, Addison-Wesley, 1998
Dan Zuras, "A nagy egészek négyzetesítéséről és szorzásáról", ARITH-11: IEEE szimpózium a számítógépes aritmetikáról, 1993, pp. 260-tól 271-ig.
DAN SSSR 150 (1963), 496-498
Richard P. Brent és Paul Zimmermann, Modern számítógépes aritmetika
Elektronikus eszközök és vezérlőrendszerek: Nemzetközi Tudományos és Gyakorlati Konferencia (2010. október 13-16.) beszámolóinak anyaga. - Tomszk: V-Spectrum, 2011: 2 óra - 2. rész - 178 p. ISBN 978-5-91191-223-6 , 123-129.

Adattípusok
Értelmezhetetlen	Bit Rágcsál Byte qubit Csemege Jellemvonás Szó
Numerikus	Egész fix pont lebegőpont Racionális Összetett Hosszú intervallum
Szöveg	Szimbolikus Húr
Referencia	Cím Link Mutató Csomagolás
Összetett	Algebrai adattípus ( általános ) Osztály Típus-termék ( Írj Tuple szerkezet ) Egy tárgy Konszolidáció ( címkézett ) Rendelt pár
absztrakt	sor Lista Fordulat Kazal Asszociatív tömb (megjelenítés, térkép ) Sok multiset típus Grafikon
Egyéb	Logikus Alsó Magasabb Polimorf Funkcionális felsorolható Gyűjtemény Kivétel nemzetség ( metaosztály ) Monád Szemafor Folyam üres
Kapcsolódó témák	Absztrakt adattípus primitív típus Adatstruktúra Generikus típusú változó Felület Konstruktor (OOP) Konstruktor (FP) Konstruktor típusa Típusöntés Prototípus Típusrendszer