Residualt talsystem

Från Wikipedia
Hoppa till: navigering, sök

Ett residualt talsystem eller residytalsystem är ett talsystem där stora heltal delas upp i en mängd mindre heltal för att vissa (dator)beräkningar ska kunna utföras mer effektivt genom att operera på varje del för sig. Systemet bygger på kinesiska restklassatsen för modulär aritmetik.

Definition[redigera | redigera wikitext]

Ett residualt talsystem definieras av en uppsättning heltal:

\{m_1, m_2, ... , m_N\}

som på engelska kallas moduli (moduler). Låt M vara den minsta gemensamma multipeln av alla m. Då kan ett godtyckligt heltal X mindre än M representeras på ett unikt sätt medelst N st mindre heltal i det residuala talsystemet.

\{x_1, x_2, ... , x_N\}

där

x_i = X \mbox{ mod } m_i

För att få en så effektiv representation som möjligt är det viktigt att alla m är relativt prima, då blir M lika med produkten av alla m.

Operationer[redigera | redigera wikitext]

Addition och multiplikation kan utföras genom att helt enkelt beräkna summan respektive produkten för de mindre heltalen. Det vill säga:

C = A+B \mbox{ mod } M

beräknas enligt

c_i = a_i + b_i \mbox{ mod } m_i

och

C = A*B \mbox{ mod } M

enligt

c_i = a_i * b_i \mbox{ mod } m_i

Exempel[redigera | redigera wikitext]

Ett residualt talsystem definieras av denna uppsättning moduler:

\{3, 5\}

Talet 6 representeras då med (0,1) och talet 2 med (2,2) (talens rest vid division med 3 respektive 5).

6+2 = (0,1)+(2,2) = (2,3) = 8
6*2 = (0,1)*(2,2) = (0,2) = 12

Dock kan man i regel inte avgöra vilket av två tal som är störst när de är skrivna enligt ett residualt talsystem. Innan man ser att (0,1) är större än (2,2) behöver man respresentera talen i något annat talsystem.

När man gör beräkningar måste man också detektera overflow vilket kan vara mycket svårt att upptäcka.