RESIDUE NUMBER SYSTEM
The history of residue number system can be linked to a verse from a third century book written
by a Chinese scholar (Sun Tzu) who posed a mathematical riddle with the following statements:
We have things we do not know the number;
If we count them by 3’s, we have two left over
If we count then by 5’s, we have three left over
If we count them by 7’s, we have two left over
How many things are there?
This riddle means which number yields remainder 2, 3, 2 when divided by 3, 5, 7 respectively.
RNS is an integer number system which speeds up arithmetic operations by splitting numbers
into smaller parts (through a set of number called moduli set) in such a way that each unit is
independent of the other. RNS allows a big number to be represented by an n-tuple of smaller
numbers that are independent of each other, where n is the number of modulus in moduli set.
Arithmetic operations are however performed on these smaller numbers independently rather
than on the original number. It is based on the congruence relation which explains that two (2)
integers a and b are said to be in congruent modulo m if m divides exactly the difference of a and
b; mathematically represented as a ≡ b(mod m). E.g 1 0 ≡4 (mod 3) .
RNS is defined in terms of a relatively prime moduli set { m1 , m2 , m 3 , … , m n } such that
gcd ( mi , m j ) =1for i≠ j, where gcd means the greatest common divisor of mi and m j while
n
M =∏ mi , is the dynamic range. The residues of a conventional number X can be obtained as
i=1
x i=¿ X ∨¿m ¿. Thus X can be represented in RNS as X =( x 1 , x 2 , x 3 , … , x n ) , 0 ≤ x i <mi.
i
RNS architectures are typically composed of three (3) main parts; a binary –to – residue
converter, residue arithmetic units and a residue – to – binary converter.
Example:
Given a moduli set {3, 4, 5}, the number 4 can be represented in RNS as:
x i=¿ X ∨¿m ¿i
x 1=¿ X ∨¿m =¿ 4∨¿3=1 ; x 2=¿ X ∨¿m =¿ 4∨¿4 =0 ; x 3=¿ X ∨¿m =¿ 4∨¿5=4 ¿ ¿ ¿ ¿ ¿ ¿
1 2 3
Thus, the RNS representation of 4 is(1 , 0 , 4)RNS(3 , 4 ,5) .
Given the moduli set {7 ,8 , 9 }, the number 150 can be represented in RNS as;
x 1=¿ X ∨¿m =¿ 150∨¿7 =3 ; x 2=¿ X∨¿ m =¿ 150∨¿8=6 ; x 3=¿ X∨¿m =¿ 150∨¿ 9=6 ¿ ¿ ¿ ¿ ¿ ¿
1 2 3
Thus, the RNS representation of 150 is thus (3 , 6 , 6)RNS(7 ,8 , 9).
ARITHMETIC OPERATIONS
The standard arithmetic operation of addition/subtraction and multiplication are easily
implemented with residue notation depending on the choice of moduli set since digit by digit
computations are allowed but division much more difficult.
Addition
Residue addition is carried out by individual adding corresponding digit, relative to the modulus
for their position, that is a carry –out from one digit position is not propagated into the next
position.
Let X and Y be represented in RNS as X =( x 1 , x 2 , x 3 , … , x n )and Y = ( y 1 , y 2 , y3 , … , y n )and
X , Y ∈ Z m=( 1 ,2 , 3 , … , M −1 )where M is the dynamic range.
Then
X +Y =Z
X +Y =¿ x 1 , x 2 , x 3 , … , x N >+¿ y 1 , y 2 , y 3 ,… , y N >¿
¿< z 1 , z 2 , z3 , … , z N > ¿
≅ Z where z i=¿ x i + y i ∨¿m ¿ i
Example: with the moduli-set { 2 , 3 ,5 , 7 }the representation of Seventeen is ¿ 1 ,2 , 2 , 3>¿ that of
19 is ¿ 1 ,1 , 4 ,5> ¿. Adding the two (2) residues relative to the modulus for their position yields
¿ 1 ,2 , 2 , 3>+¿ 1 ,1 , 4 ,5> ¿ zi =|2 ,3 ,6 , 8|m i
¿< 0 ,0 , 1 , 1> ¿
Which is the representation for thirty–six in the number system
Multiplication
Residue multiplication is performed simply by multiplying corresponding residue digit-pairs
relative to the modulus for their position; that is, multiply digits and ignore or adjust an
appropriate part of the result.
Let X and Y be represented in RNS as X =( x 1 , x 2 , x 3 , … , x n )and Y = ( y 1 , y 2 , y3 , … , y n )and
X , Y ∈ Z m=( 1 ,2 , 3 , … , M −1 )where M is the dynamic range.
Then
X ×Y =Z
X ×Y =¿ x 1 , x 2 , x 3 , … , x N >×< y 1 , y 2 , y 3 , … , y N >¿
¿< z 1 , z 2 , z3 , … , z N > ¿
≅ Z where z i=¿ x i × y i∨¿m ¿ i
From the example above, multiplying the two residue relative to the modulus for their position;
{ 2 , 3 ,5 , 7 }the representation of Seventeen is ¿ 1 ,2 , 2 , 3>¿ that of 19 is ¿ 1 ,1 , 4 ,5> ¿. Adding the
two (2) residues relative to the modulus for their position yields
z i=¿ 1 , 2, 2 , 3>×< ¿ 1 ,1 , 4 ,5> ¿
¿ z i=¿ 1 ,2 , 8 , 15∨¿ m ¿ i
¿<1 , 2 ,3 , 1>¿
Which is the representation for three hundred and twenty three (323) in the conventional number
system.
Subtraction
Residue subtraction is achieved by negating the subtrahend and adding the negation to the
minuend. This can be achieved by computing the additive inverse of the residue of the
subtrahend and adding the result to the residue of the minuend relative to the modulus for their
position.
Hence from the above example:
The additive inverse( x ) of 17 can be computed as: x=¿ m−x∨¿m ¿
|2−1|2=1
|3−2|3=1
|5−2|5=3
|7−3|7 =4
Thus, the additive inverse of ¿ 1 ,2 , 2 , 3>¿is ¿ 1 ,1 , 3 , 4> ¿
19−17=¿ 1 , 1 , 4 , 5>+¿ 1 ,2 , 2 , 3>¿
¿<1 , 1 , 4 , 5>+¿ 1 , 1, 3 , 4 >¿
¿ ¿ 2 , 2, 7 , 9∨¿m ¿ i
¿< 0 ,2 , 2 ,2> ¿
With respect to the modulus position which is the representation for 2 in the conventional
number system.
