Bignum-aritmetik

Bignum-aritmetik (ungefär stortalsaritmetik) är en teknik som gör att datorprogram kan lagra i princip hur stora tal som helst i minnet och även utföra operationer (som addition, multiplikation och division) på dem. Om man inte använder sig av bignum-aritmetik finns det gränser, om än höga, på hur stora tal datorn kan arbeta med; exakt hur stora varierar beroende på vilken typ av dator som programmet används på och vilket programspråk som används.

Bignum-aritmetik implementeras oftast genom att lagra siffrorna som talet är uppbyggt av i ett fält istället för att – som med den konventionella metoden – helt enkelt använda sig av det binära talsystemet för att representera tal. Hur stora talen kan vara begränsas då i praktiken av storleken på processorregistren. Då representeras även rationella tal av två heltal – täljaren och nämnaren – i varsitt register.

Den första stora implementeringen av bignum-aritmetik kom förmodligen i och med Maclisp (en variant av programspråket Lisp). Senare på 1980-talet kom det andra implementeringar i VAX/VMS och VM/CMS, som baserades på textsträngfunktioner eller programspråken EXEC 2 och REXX. I dagens läge stöds bignum-aritmetiken av de flesta datoralgebrasystem och moderna programspråk (bl.a. Java, Ruby och med extrabibliotek även till C/C++).

Bignum-aritmetik kallas ibland för infinite-precision arithmetic (ungefär oändlig precisionsaritmetik), vilket inte är helt sant; antalet siffror som används är ändligt, trots att talen kan bli mycket stora. Bignum-aritmetik ska inte heller blandas ihop med symbolisk beräkning, som i datoralgebrasystem, där exempelvis ${\sqrt {2}}$ räknas som ett reellt tal utan avrundning.

Denna metod är betydligt mycket långsammare än den konventionella, eftersom den sistnämnda är implementerad direkt i hårdvaran, medan bignum-aritmetik måste implementeras i mjukvaran. Därför används bignum-aritmetik vanligtvis inte till program som kräver väldigt snabba beräkningar. Ett viktigt användningsområde är inom asymmetrisk kryptering, där algoritmerna ofta använder mycket stora heltal, med tusentals siffror. Det kan också vara användbart i beräkningar där man vill ha ett mycket noggrant värde på π, något som är svårt att få med den konventionella metoden.

Fotnoter[redigera | redigera wikitext]

Knuth, Donald (1997). ”4.3.1 The Classical Algorithms”. The Art of Computer Programming Volume 2: Seminumerical Algorithms (Tredje upplagan). Addison Wesley US. ISBN 0-201-89684-2. http://www.amazon.com/Art-Computer-Programming-Seminumerical-Algorithms/dp/0201896842. Läst 2 oktober 2007