|
|
|
|
|
Residue Number SystemA residue number system (RNS) represents a large integer using a set of smaller integers, so that computation may be performed more efficiently. It relies on the Chinese Remainder Theorem of modular arithmetic for its operation, a mathematical idea generally credited to the Chinese philosopher Sun Tsu Suan-Ching in the 4th century AD. Defining a residue number system A residue number system is defined by a set of N + 1 integer constants, {m0, m1, m2, ... mN }, referred to as the moduli. The moduli must all be coprime; so in particulat no modulus may be a factor of any other. Let M be the product of all the mi. Any arbitrary integer X that smaller than M can be represented in the defined residue number system as a set of N + 1 smaller integers - {x0, x1, ... xN''}
with - xi = X modulo mi
representing the residue class of X to that modulus. The integer X can then be recovered from the set of the xi integers. Operations on RNS Numbers Once represented in RNS, many arithmetic operations can be efficiently performed on the encoded integer. For the following operations, consider two integers, A and B, represented by ai and bi in an RNS system defined by mi (for i from 0 ≤ i ≤ N). Addition and subtraction Addition can be accomplished by simply adding the small integer values together, modulo their specific moduli. For example, a sum can be computed by calculating a set of sumi values such that: - sumi = ( ai + bi ) % mi
Similarly, subtraction works the same way: - diffi = (ai - bi ) % mi
Multiplication Multiplication can be accomplished in a manner similar to addition and subtraction. To calculate PROD = A * B, we can calculate: - prodi = ( ai * bi ) % mi
Practical applications RNS have a practical application in the field of digital computer arithmetic. By decomposing in this a large integer into a set of smaller integers, a large calculation can be performed as a series of smaller calculations that can be performed independently and in parallel.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|