Residualt talsystem

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

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\text{ 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

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\text{ mod }M$

beräknas enligt

$c_i=a_i+b_i\text{ mod }{m}_i$

och

$C=A*B\text{ mod }M$

enligt

$c_i=a_i*b_i\text{ mod }{m}_i$

Exempel

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.