Aritmetika libovolné přesnosti - Arbitrary-precision arithmetic

Ve výpočetní techniky , výpočty s libovolnou přesností , také nazývaný bignum aritmetiky , více přesné aritmetický , nebo někdy nekonečně přesnost aritmetické , znamená, že výpočty jsou prováděny na čísla, jejichž číslice o přesnosti jsou omezeny pouze dostupné paměti hostitelského systému. To je v kontrastu s rychlejší aritmetikou s pevnou přesností, která se nachází ve většině hardwaru aritmetické logické jednotky (ALU), která obvykle nabízí přesnost 8 až 64 bitů .

Několik moderních programovacích jazyků má vestavěnou podporu pro bignumy a jiné mají k dispozici knihovny pro celočíselnou a matematiku s plovoucí desetinnou čárkou s libovolnou přesností . Spíše než ukládat hodnoty jako pevný počet bitů související s velikostí registru procesoru , tyto implementace obvykle používají pole číslic s proměnnou délkou .

Libovolná přesnost se používá v aplikacích, kde rychlost aritmetiky není omezujícím faktorem nebo kde jsou vyžadovány přesné výsledky s velmi velkým počtem. Nemělo by být zaměňováno se symbolickým výpočtem poskytovaným mnoha systémy počítačové algebry , které reprezentují čísla výrazy jako $π \cdot sin (2)$ , a mohou tedy představovat libovolné vypočítatelné číslo s nekonečnou přesností.

Aplikace

Běžnou aplikací je kryptografie s veřejným klíčem , jejíž algoritmy běžně používají aritmetiku s celými čísly se stovkami číslic. Další je v situacích, kdy by umělé limity a přetoky nebyly vhodné. Je také užitečný pro kontrolu výsledků výpočtů s pevnou přesností a pro stanovení optimálních nebo téměř optimálních hodnot pro koeficienty potřebné ve vzorcích, například √ ⅓, které se objevují v Gaussově integraci .

Libovolná přesná aritmetika se také používá k výpočtu základních matematických konstant, jako jsou π až miliony nebo více číslic, a k analýze vlastností číslicových řetězců nebo obecněji ke zkoumání přesného chování funkcí, jako je funkce Riemannova zeta, kde je obtížné určit určité otázky prozkoumejte pomocí analytických metod. Dalším příkladem je vykreslování fraktálních obrazů s extrémně vysokým zvětšením, jaké se nacházejí v sadě Mandelbrot .

Arbitmetiku s libovolnou přesností lze také použít k zamezení přetečení , což je inherentní omezení aritmetiky s pevnou přesností. Podobně jako 5místný displej počítadla ujetých kilometrů, který se mění z 99999 na 00000, může celé číslo s pevnou přesností vykazovat zalamování, pokud čísla rostou příliš velká na to, aby je bylo možné reprezentovat na pevné úrovni přesnosti. Některé procesory mohou místo toho řešit přetečení saturací , což znamená, že pokud by byl výsledek nereprezentovatelný, bude nahrazen nejbližší reprezentovatelnou hodnotou. (Při 16bitové sytosti bez znaménka by přidání jakékoli kladné částky na 65535 přineslo 65535.) Některé procesory mohou generovat výjimku, pokud aritmetický výsledek překročí dostupnou přesnost. V případě potřeby lze výjimku zachytit a obnovit-například operaci lze restartovat v softwaru pomocí aritmetiky s libovolnou přesností.

V mnoha případech může úkol nebo programátor zaručit, že celočíselné hodnoty v konkrétní aplikaci nebudou dostatečně velké, aby způsobily přetečení. Takové záruky mohou být založeny na pragmatických limitech: školní docházkový program může mít limit úkolů 4 000 studentů. Programátor může navrhnout výpočet tak, aby mezivýsledky zůstaly v rámci zadaných hranic přesnosti.

Některé programovací jazyky jako Lisp , Python , Perl , Haskell a Ruby používají nebo mají možnost použít čísla libovolné přesnosti pro celou celočíselnou aritmetiku. Ačkoli to snižuje výkon, eliminuje to možnost nesprávných výsledků (nebo výjimek) kvůli jednoduchému přetečení. Umožňuje také zaručit, že aritmetické výsledky budou stejné na všech počítačích, bez ohledu na velikost slova konkrétního stroje . Výhradní použití čísel s libovolnou přesností v programovacím jazyce také zjednodušuje jazyk, protože číslo je číslo a není potřeba, aby více typů reprezentovalo různé úrovně přesnosti.

Problémy s implementací

Aritmetika s libovolnou přesností je podstatně pomalejší než aritmetika pomocí čísel, která se zcela vejdou do registrů procesoru, protože ty jsou obvykle implementovány v hardwarové aritmetice, zatímco první musí být implementována v softwaru. I když počítač postrádá hardware pro určité operace (například celočíselné dělení nebo všechny operace s plovoucí desetinnou čárkou) a místo toho je k dispozici software, bude používat velikosti čísel úzce související s dostupnými hardwarovými registry: pouze jedno nebo dvě slova a rozhodně ne N slova. Existují výjimky, protože některé stroje s proměnnou délkou slova z 50. a 60. let, zejména z řad IBM 1620 , IBM 1401 a Honeywell Liberator , mohly manipulovat s čísly vázanými pouze dostupným úložištěm, navíc s bitem, který hodnotu ohraničoval.

Čísla mohou být uložena ve formátu s pevnou řádovou čárkou nebo ve formátu s plovoucí desetinnou čárkou jako význam vynásobený libovolným exponentem. Protože však dělení téměř okamžitě zavádí nekonečně se opakující posloupnosti číslic (například 4/7 v desítkové soustavě nebo 1/10 v binární), pokud by tato možnost nastala, pak by buď byla reprezentace zkrácena na nějakou uspokojivou velikost, nebo by byla racionální čísla použité: velké celé číslo pro čitatele a pro jmenovatele . Ale i když je největší společný dělitel rozdělen, aritmetika s racionálními čísly se může velmi rychle stát nepraktickou: 1/99 - 1/100 = 1/9900, a když se pak přidá 1/101, výsledek je 10001/999900.

Velikost čísel s libovolnou přesností je v praxi omezena celkovým dostupným úložištěm a dobou výpočtu.

Byla vyvinuta řada algoritmů pro efektivní provádění aritmetických operací s čísly uloženými s libovolnou přesností. Zejména za předpokladu, že $N$ jsou použity číslice, algoritmy byly navrženy tak, aby se minimalizovalo asymptotické složitost pro velké $N$ .

Nejjednodušší algoritmy jsou pro sčítání a odčítání , kde se jednoduše sčítají nebo odčítají číslice v pořadí, přičemž se přenáší podle potřeby, čímž se získá $O (N)$ algoritmus (viz velká O notace ).

Porovnání je také velmi jednoduché. Porovnávejte číslice vyššího řádu (nebo strojová slova), dokud není nalezen rozdíl. Porovnání zbývajících číslic/slov není nutné. Nejhorší je $($ $N$ $)$ , ale obvykle to půjde mnohem rychleji. ${\ displaystyle \ Theta}$

Pokud jde o násobení , nejjednodušší algoritmy používané pro ruční násobení čísel (jak se vyučuje na základní škole) vyžadují operace $($ $N$ $2$ $)$ , ale multiplikační algoritmy, které dosahují složitosti $O ($ $N$ $log ($ $N$ $) log (log ($ $N$ $))),$ byly vymyslel, jako je Schönhage-Strassen algoritmus , založený na rychlá Fourierova transformace , a tam jsou také algoritmy s mírně horší složitosti, ale s někdy vynikající reálném světě představení pro menší $N$ . Karatsuba násobení je takový algoritmus. ${\ displaystyle \ Theta}$

Pro dělení , viz divize algoritmus .

Seznam algoritmů spolu s odhady složitosti najdete ve výpočetní složitosti matematických operací .

Příklady v sestavení x86 najdete v externích odkazech .

Přednastavená přesnost

V některých jazycích, jako je REXX , musí být před provedením výpočtu nastavena přesnost všech výpočtů. Jiné jazyky, jako například Python a Ruby , automaticky zvyšují přesnost, aby se zabránilo přetečení.

Příklad

Výpočet faktoriálů může snadno produkovat velmi velká čísla. To není problém pro jejich použití v mnoha vzorcích (například v Taylorových řadách ), protože se objevují společně s dalšími výrazy, takže - při pečlivém zvážení pořadí vyhodnocování - nejsou mezilehlé výpočtové hodnoty problematické. Pokud jsou požadovány přibližné hodnoty faktoriálních čísel, Stirlingova aproximace poskytuje dobré výsledky pomocí aritmetiky s plovoucí desetinnou čárkou. Největší reprezentovatelnou hodnotu pro celočíselnou proměnnou s pevnou velikostí lze překročit i pro relativně malé argumenty, jak je uvedeno v tabulce níže. I čísla s plovoucí desetinnou čárkou jsou brzy překonána, takže může pomoci přepracování výpočtů z hlediska logaritmu čísla.

Ale pokud jsou požadovány přesné hodnoty pro velké faktoriály, pak je vyžadován speciální software, jako v následujícím pseudokódu, který implementuje klasický algoritmus pro výpočet 1, 1 × 2, 1 × 2 × 3, 1 × 2 × 3 × 4, atd. postupná čísla faktoriálů.

Constant Limit = 1000;            % Sufficient digits.
Constant Base = 10;               % The base of the simulated arithmetic.
Constant FactorialLimit = 365;    % Target number to solve, 365!
Array digit[1:Limit] of integer;  % The big number.
Integer carry,d;                  % Assistants during multiplication.
Integer last,i;                   % Indices to the big number's digits.
Array text[1:Limit] of character; % Scratchpad for the output.
Constant tdigit[0:9] of character = ["0","1","2","3","4","5","6","7","8","9"];
BEGIN
 digit:=0;                        % Clear the whole array.
 digit[1]:=1;                     % The big number starts with 1,
 last:=1;                         % Its highest-order digit is number 1.
 for n:=1 to FactorialLimit do    % Step through producing 1!, 2!, 3!, 4!, etc. 
  carry:=0;                       % Start a multiply by n.
  for i:=1 to last do             % Step along every digit.
   d:=digit[i]*n + carry;         % The classic multiply.
   digit[i]:=d mod Base;          % The low-order digit of the result.
   carry:=d div Base;             % The carry to the next digit.
  next i;
  while carry > 0                 % Store the carry in the big number.            
   if last >= Limit then croak("Overflow!");  % If possible!
   last:=last + 1;                % One more digit.
   digit[last]:=carry mod Base;   % Placed.
   carry:=carry div Base;         % The carry reduced.
  Wend                            % With n > Base, maybe > 1 digit extra.
  text:=" ";                      % Now prepare the output.
  for i:=1 to last do             % Translate from binary to text.
   text[Limit - i + 1]:=tdigit[digit[i]];  % Reversing the order.
  next i;                         % Arabic numerals put the low order last.
  Print text," = ",n,"!";         % Print the result!
 next n;                          % On to the next factorial up.
END;

S ukázkovým příkladem lze diskutovat o řadě podrobností. Nejdůležitější je volba reprezentace velkého čísla. V tomto případě jsou pro číslice vyžadovány pouze celočíselné hodnoty, takže pole celých čísel s pevnou šířkou je dostačující. Je vhodné, aby po sobě jdoucí prvky pole představovaly vyšší síly základny.

Druhé nejdůležitější rozhodnutí je ve výběru základny aritmetiky, zde deset. Existuje mnoho úvah. Proměnná $d$ scratchpad $d$ musí být schopna pojmout výsledek jednociferného násobení plus vynášení z násobení předchozí číslice. V základně deset je šestnáctibitové celé číslo zcela dostačující, protože umožňuje až 32 767. Tento příklad však podvádí, protože hodnota $n$ není sama omezena na jedinou číslici. To má za následek, že metoda selže pro $n > 3200$ nebo tak. V obecnější implementaci by $n$ také používalo vícecifernou reprezentaci. Druhým důsledkem zkratky je, že poté, co bylo dokončeno víceciferné násobení, bude možná nutné provést poslední hodnotu přenosu do několika číslic vyššího řádu, nikoli pouze do jedné.

Existuje také otázka tisku výsledku v desítce, pro lidskou úvahu. Vzhledem k tomu, že bází je již deset let, by mohl být výsledek zobrazen pouze vytištěním po sobě následujících číslic pole číslic , ale zdá se nejvyšší pořadí číslici poslední (takže 123 se jeví jako „321“). Celé pole by bylo možné vytisknout v opačném pořadí, ale to by představovalo číslo s úvodními nulami („00000 ... 000123“), což nemusí být oceněno, takže tato implementace vytváří reprezentaci v textové proměnné s mezerou a pak tiskne že. Prvních několik výsledků (s mezerami mezi každou pátou číslicí a poznámkami přidanými zde) jsou:

Faktorová čísla		Dosah počítačových celých čísel
1 =	1!
2 =	2!
6 =	3!
24 =	4!
120 =	5!	8bitové	255
720 =	6!
5040 =	7!
40320 =	8!	16bitové	65535
3 62880 =	9!
36 28800 =	10!
399 16800 =	11!
4790 01600 =	12!	32bitové	42949 67295
62270 20800 =	13!
8 71782 91200 =	14!
130 76743 68000 =	15!
2092 27898 88000 =	16!
35568 74280 96000 =	17!
6 40237 37057 28000 =	18!
121 64510 04088 32000 =	19!
2432 90200 81766 40000 =	20!	64bitové	18446 74407 37095 51615
51090 94217 17094 40000 =	21!
11 24 000 72777 76076 80000 =	22!
258 52016 73888 49766 40000 =	23!
6204 48401 73323 94393 60000 =	24!
1 55112 10043 33098 59840 00000 =	25!
40 32914 61126 60563 55840 00000 =	26!
1088 88694 50418 35216 07680 00000 =	27!
30488 83446 11713 86050 15040 00000 =	28!
8 84176 19937 39701 95454 36160 00000 =	29!
265 25285 98121 91058 63630 84800 00000 =	30!
8222 83865 41779 22817 72556 28800 00000 =	31!
2 63130 83693 36935 30167 21801 21600 00000 =	32!
86 83317 61881 18864 95518 19440 12800 00000 =	33!
2952 32799 03960 41408 47618 60964 35200 00000 =	34!	128bitové	3402 82366 92093 84634 63374 60743 17682 11455
1 03331 47966 38614 49296 66651 33752 32000 00000 =	35!

Tato implementace by mohla účinněji využívat vestavěnou aritmetiku počítače. Jednoduchou eskalací by bylo použití báze 100 (s odpovídajícími změnami v procesu překladu pro výstup) nebo s dostatečně širokými počítačovými proměnnými (jako jsou 32bitová celá čísla) bychom mohli použít větší základny, například 10 000. Práce v základně o výkonu 2 blíže integrovaným celočíselným operacím počítače nabízí výhody, přestože převod na desítkovou základnu pro výstup je obtížnější. Na typických moderních počítačích trvá sčítání a násobení konstantní čas nezávislý na hodnotách operandů (pokud se operandy vejdou do jednotlivých strojových slov), takže je velkým přínosem zabalit do každého prvku co nejvíce bignumberu. číselné pole. Počítač může také nabídnout zařízení pro rozdělení produktu na číslici a přenos, aniž by vyžadoval dvě operace mod a div, jako v příkladu, a téměř všechny aritmetické jednotky poskytují příznak přenosu, který lze využít při sčítání a odčítání s více přesností. Tento druh detailů je podstatou programátorů strojového kódu a vhodná rutina bignumber v jazyce sestavení může běžet mnohem rychleji než výsledek kompilace jazyka na vysoké úrovni, který neposkytuje přístup k takovým zařízením.

Pro jednociferné násobení musí být pracovní proměnné schopny pojmout hodnotu (základ-1) ² + přenos, kde maximální hodnota přenosu je (základ-1). Podobně proměnné použité k indexování číselného pole jsou samy omezeny na šířku. Jednoduchý způsob, jak rozšířit indexy, by bylo vypořádat se s číslicemi velkého čísla v blocích nějaké vhodné velikosti, takže adresování by bylo přes (blok i , číslice j ), kde i a j by byla malá celá čísla, nebo by bylo možné eskalovat na používající techniky indexování proměnných. Nakonec kapacita úložiště stroje a doba provádění omezují velikost problému.

Dějiny

První obchodní počítač IBM , IBM 702 ( elektronkový stroj) z poloviny padesátých let, implementoval celočíselnou aritmetiku zcela v hardwaru na číslicových řetězcích libovolné délky od 1 do 511 číslic. Nejdříve rozšířená softwarová implementace aritmetiky s libovolnou přesností byla pravděpodobně v Maclispu . Později, kolem roku 1980, operační systémy VAX/VMS a VM/CMS nabízely zařízení bignum jako soubor řetězcových funkcí v jednom případě a v jazycích EXEC 2 a REXX v druhém případě.

Brzy rozšířená implementace byla k dispozici prostřednictvím IBM 1620 z let 1959–1970. 1620 byl stroj s desítkovými číslicemi, který používal diskrétní tranzistory, ale měl hardware (který používal vyhledávací tabulky ) k provádění celočíselné aritmetiky na číslicových řetězcích o délce, která mohla být od dvou do jakékoli dostupné paměti. U aritmetiky s pohyblivou řádovou čárkou byla mantisa omezena na sto číslic nebo méně a exponent byl omezen pouze na dvě číslice. Největší dodávaná paměť nabízela 60 000 číslic, nicméně kompilátory Fortran pro 1620 se usadily na pevných velikostech, jako je 10, i když by to mohlo být uvedeno na kontrolní kartě, pokud by výchozí nastavení nebylo uspokojivé.

Softwarové knihovny

Aritmetika libovolné přesnosti je ve většině počítačového softwaru implementována voláním externí knihovny, která poskytuje datové typy a podprogramy pro ukládání čísel s požadovanou přesností a pro provádění výpočtů.

Různé knihovny mají různé způsoby reprezentace čísel s libovolnou přesností, některé knihovny pracují pouze s celočíselnými čísly, jiné ukládají čísla s plovoucí desetinnou čárkou na různé báze (desítkové nebo binární mocniny). Spíše než reprezentovat číslo jako jednu hodnotu, některé ukládají čísla jako pár čitatel/jmenovatel ( racionální ) a některé mohou plně reprezentovat vyčíslitelná čísla , i když pouze do určitého limitu úložiště. Podstatnější je, že Turing stroje nemůže představovat všechna reálná čísla , jak mohutnost z $ℝ$ přesahuje mohutnost $ℤ$ .

Viz také

Reference

Knuth, Donald (2008). Seminumerické algoritmy . Umění počítačového programování . 2 (3. vyd.). Addison-Wesley. ISBN 978-0-201-89684-8{{nekonzistentní citace}}CS1 maint: postscript ( odkaz ), Oddíl 4.3.1: Klasické algoritmy

externí odkazy

Kapitola 9.3 Umění montáže od Randall Hyde pojednává o aritmetice s více přesnostmi, s příklady v sestavě x86 .
Úloha Rosetta Code Celá čísla s libovolnou přesností Případové studie ve stylu, ve kterém více než 95 programovacích jazyků vypočítá hodnotu 5 ** 4 ** 3 ** 2 pomocí aritmetiky s libovolnou přesností.

Languages

In other projects