11 Hardware Realization of Arithmetic Operations
239
Fig. 11.1 Common structure of RNS
the appropriate index, i.e., A + B = ((A 1 + B 1 ) mod p 1 , (A 2 + B 2 ) mod p 2 ,
(A 3 + B 3 ) modp 3 ) = (2, 1, 0) = S.
There are a couple of ways to convert a number S into a positional number. The
most common one is based on the following formula:
Z =(X 1 · Y 1 + X 2 · Y 2 + . . . + X n · Y n ) mod P
=X 1 · Y 1 + X 2 · Y 2 + . . . + X n · Y n − k · P ,
(11.1)
where k is a natural number and Y i =
P
p i
· q, where q should satisfy the condition
q ·
P
p i
(mod p i ) = 1, i = 1, 2, . . . , n and q = 1, 2, . . . , p i − 1.
By this formula
S = 2 · 70 + 1 · 21 + 0 · 15 = 161 − 1 · 105 = 56,
where: Y 1 =
105
3 · 2, because 2 ·
105
3 (mod 3) = 1; Y 2 =
105
5 · 1, because 1 ·
105
5 (mod 5) = 1; Y 3 =
105
7 · 1, because 1 ·
105
7 (mod 7) = 1.
There are a couple of significant limits of RNS implementation for wide
range computing, namely the conversion from the positional system to RNS and
backward. In fact, no one electronic design automation (EDA) tool (but Synopsys)
can generate a circuit to compute the modulus function. The exception is when
modulus P = 2 δ , where δ is a natural number, because an arbitrary number with
modulus 2 δ equals the δ least significant bits of this number. Otherwise, the problem
is computationally hard. Backward conversion is slightly easier, because it consists
of multipliers and summators (as shown in formula (11.1)). But, eventually, either
the modulus function with modulo P must be computed or a comparison with the
value k · P must be performed many times in order to find k, or the conventional
239
Fig. 11.1 Common structure of RNS
the appropriate index, i.e., A + B = ((A 1 + B 1 ) mod p 1 , (A 2 + B 2 ) mod p 2 ,
(A 3 + B 3 ) modp 3 ) = (2, 1, 0) = S.
There are a couple of ways to convert a number S into a positional number. The
most common one is based on the following formula:
Z =(X 1 · Y 1 + X 2 · Y 2 + . . . + X n · Y n ) mod P
=X 1 · Y 1 + X 2 · Y 2 + . . . + X n · Y n − k · P ,
(11.1)
where k is a natural number and Y i =
P
p i
· q, where q should satisfy the condition
q ·
P
p i
(mod p i ) = 1, i = 1, 2, . . . , n and q = 1, 2, . . . , p i − 1.
By this formula
S = 2 · 70 + 1 · 21 + 0 · 15 = 161 − 1 · 105 = 56,
where: Y 1 =
105
3 · 2, because 2 ·
105
3 (mod 3) = 1; Y 2 =
105
5 · 1, because 1 ·
105
5 (mod 5) = 1; Y 3 =
105
7 · 1, because 1 ·
105
7 (mod 7) = 1.
There are a couple of significant limits of RNS implementation for wide
range computing, namely the conversion from the positional system to RNS and
backward. In fact, no one electronic design automation (EDA) tool (but Synopsys)
can generate a circuit to compute the modulus function. The exception is when
modulus P = 2 δ , where δ is a natural number, because an arbitrary number with
modulus 2 δ equals the δ least significant bits of this number. Otherwise, the problem
is computationally hard. Backward conversion is slightly easier, because it consists
of multipliers and summators (as shown in formula (11.1)). But, eventually, either
the modulus function with modulo P must be computed or a comparison with the
value k · P must be performed many times in order to find k, or the conventional