Determining the rank of a number in the residue number system

Abstract

In this article, the formulation and proof of the theorem on the di erence in the ranks of the numbers represented in the Residue Number System is carried out. A method is proposed that allows to reduce the amount of necessary calculations and increases the speed of calculating the rank of a number relative to the method for calculating the rank of a number based on the approximate method. To nd the rank of a number in the method for calculating the rank of a number based on the approximate method, it is necessary to calculate n operations with numbers exceeding the modulus value; in the proposed method, it is necessary to calculate n (n 1) operations not exceeding the value of the module. 2

1. Introduction

The current state of development of infocommunication technologies in the eld of data processing and transmission is characterized by the intensive introduction of new principles and approaches to information processing. One of the ways to increase the speed of computing facilities led to the creation of computing systems with a parallel structure. At the same time, it became necessary and expedient to use codes with a parallel structure. These codes include non-weigted codes - codes based on modular arithmetic, that is, codes in which numbers are represented in the Residue Number System (RNS) [1].

The Residue Number System is a number system based on the representation of a number as a set of residues after division by a set of coprime numbers, called the basis of the system. The main feature of the RNS is the non-weighted representation of a number, which ensures the independence of numeric digits and the possibility of parallel processing of numbers [2, 3]. where Pi = pPi . The numbers Bi = Pi 1 pi Pi is customary to call orthogonal RNS bases since their representation in RNS corresponds to the number 1 in position i and 0 in positions j 6= i.

The advantage of the modular representation of a number is that the operations of addition, subtraction and multiplication are very simple and parallel. [6]. Let the numbers A and B be given by the formula ( 1 ):

A B 1 (modp1) ; A 1 (modp1) ; B 2 (modp2) ; : : : ; A 2 (modp2) ; : : : ; B n (modpn) n (modpn)

Then the operations of addition, multiplication and subtraction can be performed according to the formulas ( 1 ) ( 2 ) ( 3 )

Let the RNS be given by a set of coprime bases p1; p2; : : : ; pn. Then the number X can be represented as X = (x1; x2; : : : ; xn), where xi = jXjpi for all i = 1; 2; : : : ; n [4]. The numbers xi will be called the digits of the number X in this RNS. According to the Chinese remainder theorem, the RNS allows a unique representation of any number from the interval [0; P ), where P = p1 p2 : : : pn { is a dynamic range of number representation [5].

The fundamental proposition underlying modular arithmetic is the Chinese Remainder

Theorem:

Theorem 1: Let p1; p2; : : : ; pk be some natural coprime numbers and P = p1 p2 : : : pk. Any number X, such that 0 X P , can be unambiguously represented as a sequence (x1; x2; : : : ; xn), where xi = X mod pi, wherein

n X = X Pi 1 i=1 pi

Pixi ;

P = ((( 1 = ((( 1

A B = ( 1; 2; : : : ; n) ( 1; 2; : : : ; n) = 1) (modp1)) ; (( 2 2) (modp2)) ; : : : ; (( n

n) (modpn)))

A B = ( 1; 2; : : : ; n) ( 1; 2; : : : ; n) = 1) (modp1)) ; (( 2 2) (modp2)) ; : : : ; (( n n) (modpn)))

The operations of addition, subtraction and multiplication in the RNS are performed independently and in parallel, therefore, based on this number system, it is possible to create a completely homomorphic coding system. Coding systems of this type are required when organizing cloud computing, since they allow protecting data when performing mathematical operations remotely [7].

The range of numbers on which modular arithmetic operations can be performed is the set n of numbers P , each of which does not exceed the product of the selected moduli Q pi [8, 9]. i=1 2. Algorithm for calculating the rank of a number based on the approximate method In order to simplify the process of converting numbers from the modular representation to the positional representation of numbers, we will consider an approximate method that allows to go from the expensive operation of taking the remainder in a large modulus to taking the fractional part of a number by replacing the exact value with an approximate one, and completely correctly implement the main classes of decision-making procedures: checking the equality (inequality) of two values; comparison of two values (more, less) that provide a solution to the main range of problems arising from the hardware or software implementation of real processes [10].

The essence of the approximate method is to use the relative value of the original number to the full range of CRT, which connects the positional number X with its representation in the residues (x1; x2; : : : ; xn) by the following expression [6]: where xi are the smallest nonnegative residues of a number divided by moduli of the RNS n p1; p2; : : : ; pn, P = iQ=1 pi, Pi 1 pi is multiplicative inversion Pi relative to pi and for all i = 1; n the equality P = pPi .

If the formula ( 4 ) is divided by the RNS range P , then we get an approximate value: X =

Xn P i=1 pi

P 1 i pi xi ;

P X P

n = X i=1

P 1 i pi pi xi ;

1 n where SQ = P Pi.

i=1 ( 6 ) ( 7 ) where for all i = 1; n the equation jPi 1jpi are the constants of the selected system, and xi pi are digits of the number presented in the RNS, while the value of each sum is in the interval [0; 1). The nal result of the sum is determined after summing and discarding the integer part of the number, keeping the fractional part of the sum. The fractional part can also be written as X mod 1, because X = bXc + X mod 1. The number of digits of the fractional part of a number is determined by the maximum possible di erence between adjacent numbers. In the work [11] it is shown that with a computational accuracy of N bits, the recovery of numbers by n the formula (5 is correct, where N = dlog2 ( P )e and = n + P pi. i=1

The hardware implementation of the arithmetic operations of multiplication and addition of real numbers requires on average 3.5 times more hardware resources than performing the same operations with integers of the same size, so we make the transition from real numbers to integers, and the formula ( 5 ) takes view: 6 n 6 P kixi 6 X = 666 i=1 4 2N 2N

7 P 77 7 7 ; 7 5 where ki = & jPi 1jpi 2N ' pi

.

Then the operation of taking the fractional part in the formula ( 5 ) will be replaced by the operation of taking the least signi cant N bits of the number in the formula ( 6 ), and the operation of taking the residue from division by the large modulus of the RNS range P will be replaced with multiplication and shift to the right by N bits of the number.

Let us investigate the question of the size N . Theorem 2: [12] The formula (6) is true if N is chosen equal to:

n n 1 jPi 1jpi 2N ! i=P21 kixi iP=1 pi + Ri xi = = iP=n1 jPi 1pjipi 2N xi + iP=n1 Rixi = 2N iP=n1 jPi 1pjipi 2N xi + iP=n1 Rixi: n X kixi i=1 2N

n = X kixi i=1 $Xn kixi % i=1 2N 2N

Substituting (8) in (9) we get:

n X kixi i=1 2N

n = 2N X i=1 Substituting the formula ( 10 ) to the right side of the formula ( 6 ), we get: 6 n 6 P kixi 6 66 i=1 6 2N 4 2n

P 777 66 n 777 = 66P X 5 4 i=1 Taking into account that by the Chinese remainder theorem:

n X = P X i=1

Conditions 1 and 2 are equivalent, therefore, it is necessary and su cient for the following condition to be satis ed: It follows from the inequality (13) that a necessary and su cient condition is: n 2N > P X Rixi

i=1

Estimating the right side of the inequality (14), we obtain:

n n P P Rixi < P P mi 1 (mi i=1 i=1 nmi = nP + P P mi i=1 nP + SQ =

n 1) = P P (m1 i=1 1)

n P P i=1 1 1 mi

= n 2n + P mi P + SQ: i=1 It follows from the formula (15) and inequality (14), that if we choose

To do this, let's nd the di erence

n 2n + P pi P + SQ i=1

dlog2 ( P )e.

P

From the formula (16) it follows that the obtained estimate of the value of N is more accurate than the estimate from the work [11].

According to the Chinese Remainder Theorem, the value of X can be calculated by the formula ( 4 ) or:

n X = X Pi Pi 1 i=1 pi xi jPi 1jpi 2N1

pi .

Let us examine the question of the relationship between the values N1, r and rX . Theorem 3: (14) (15) (17) (18) (i) If N1 = N , then rX = r. (ii) If N1 = dlog2 e, then rX = r or rX = r

1, where

n = P pi i=1

Proof

Substituting the formula (18) in (19), we get

jPi 1pjpii2N1 + R0! xi = iP=n1 jPi 1pjpii2N1 xi + iP=n1 Ri0xi = = 2N1 Pn jPi 1jpi xi + P Ri0xi

n i=1 pi i=1 r = 466666 iP=n21Nk1ixi 577777 = 666664Xi=n1 Pipi1 pi xi + iP=n12NR1i0xi 777775 (19) (20)

From formulas (17) and (20) it follows, that r = rx for iP=21NR1i0xi < P1 . According to the theorem 3, this inequality holds for N1 = N .

If rx = r or rx = r 1, than from the formula (20) it follows that a su cient condition is n n iP=1 Ri0xi 2N1

n < 1, therefore, P Ri0xi < 2N1.

i=1 Let the numbers X ! f16; 18; 22; 24g and Y ! f1; 2; 3; 4g be given in the RNS. 1. We calculate the values X and Y using the approximate method. 2. We calculate the values X and Y based on theorem 1 and the rank of the function by the formula (18). 3. We calculate the values X and Y using the 1 theorem and the rank of the number calculated using the approximate method with accuracy N .

n P kixi = 16 13816531 + 18 15011194 + 22 8753331 + 24 12750685 = 989855710 i=1

0, then the result remains unchanged. 3. Algorithm for calculating the di erence in the ranks of a number in the Residue Number System Let a system be given with bases p1; p2; : : : ; pn, the range P of which is de ned as P = Qin=n pi. Any number A from the range [0; P ) can be represented uniquely for the chosen bases A = ( 1; 2; : : : ; n).

The given system of bases uniquely corresponds to the system of orthogonal bases B1; B2; : : : ; Bn such that the value A in weigted number system can be represented as or

A n X iBi (mod P ) i=1

n A = X i=1 iBi r(A)P; where r(A) is a positive integer showing how many times the range of the system P was exceeded in transition the representation of a number from the RNS to its positional representation in a system of orthogonal bases.

The positive integer rA will be called the rank of the number A.

The rank of a number is used for implementation of the following operations: detection of dynamic range over ow, converting a number from RNS to binary representation, comparing a number, etc. The increasing demands for the speed of devices lead to the need to improve the performance of all operations. This work is devoted to the development of an e ective method for calculating the rank of a number in RNS.

Theorem 4: If X ! (x1; x2; : : : ; xn) and Y ! (y1; y2; : : : ; yn) given in RNS with bases p1; p2; : : : ; pn satisfy the following conditions: 0 X < P , 0 Y < P and X + Y < P , then the formula (22) is correct.

r (X + Y ) = r (X) + r (Y )

X xi+yi 0

P 1 i pi Let us formulate a theorem on the rank of the di erence of two numbers.

Theorem 5: If X ! (x1; x2; : : : ; xn) and Y ! (y1; y2; : : : ; yn) given in RNS with bases p1; p2; : : : ; pn satisfy the following conditions: 0 X < P , 0 Y < P and 0 X Y < P , then the formula (23) is correct.

Proof: Calculating r (X Y ), we get:

r (X yijpi can be calculated by the formula: jxi yijpi = xi xi yi + pi if xi < yi; yi otherwise; then (24) is transformed to:

Considering that for any m 2 Z and a 2 R the equality holds bm + ac = m + bac and Pxi<yi Pi 1 pi 2 Z, the formula (26) takes the form: (21) (22) (23) (24) (25) (26) Since P 2 Z, then r (X n pi xi

Pn i=1 Pi Pi

pi P

Since by the condition of the theorem 0

X Y < 0, then the term in (31) s equal

j X

P

Y k P to zero. Considering that 6 r (X) = 6 4

P P 1 1 pi pi

7 xi 7 7 7 5

Substituting (28) and (29) in (27), we get:

According to the Chinese Remainder Theorem,

Pn i=1 Pi Pi 1 = Y , therefore (30) takes the form:

Pn i=1 Pi Pi 1 pi xi

P =

X and pi yi

P r (X

6 Y ) = 6 4 6 6 Pn i=1 Pi Pi

1 +

X P

Y P

P +

pi X xi<yi

7 6 xi 7 6 Pin=1 Pi Pi 7 6 7 6 5 4 P 1 pi

7 yi 7 7 7 + 5 P i 1 pi 1 1 pi pi Proof: Calculating the value r (X) by the formula (32), we get: r (X) = pj r (Y )

66 Pin=1 Pi Pi 1 r (X) = 66 4 P

Since for any i the equation xi = jpj yijpi = pj yi pi j pjpiyi k holds, then (36) is transformed to: r (X) = (34) (35) (36) (37) (38)

pi pi yi = P r (Y ) + Y , therefore the formula (37) is transformed to: r (X) = pj P r (Y ) + pj Y

P = pj r (Y ) + pj Y

P n X P 1

i i=1

pi n X P 1

i i=1 pi pj yi pi pj yi pi = the inequality 0 formula (38) is transformed to:

It follows from the condition of the theorem that X = pj Y and X 2 ZP , therefore X satis es X < P , hence the term j pjPY k in the formula (38) is equal to zero, and the r (X) = pj r (Y ) n X P 1

i pj yi ri = r (i) 8 : i = 1; pn, where Pi = P=pi 8 : i = 1; n.

Output r (X). x( 1 ) = 0;

1 For j = 2, j n, j + + do

x(j1) = jxj x1jpj ; yj( 1 ) = w1;j x(j1) pj For i = 2, i < n, i + + do x(i) = 0;

i For j = i + 1, j x(ji) = yj(i 1) n, j + + do

yi(i 1) pj ; yj(i) = wi;j x(ji) pj r = pn 1 r yn(n 1)

= pn 1 ryn(n 1) ; For j = 1, j < n, j + + do yj(n 1) = yn(n 1) ; Parallel processing

pj x(n 1) = pn 1 y(n 1) j j ; r = r

Bj 1, i

pj do For i = n 2, i rmult = 0; radd = 0; For j = 1, j

n, j + + do yj(i) = x(ji) + yi(+i)1 pj ; Parallel processing If x(ji) + yi(+i)1 pj Then

radd = radd + Bj ; r = r + ryi(+i)1 x(ji) = pi yj(i) pj ; rmult = rmult + Bj

radd; r = pi r rmult;

The theorem is proved.

Using the theorems 5, 6 and the formula (22) we propose an algorithm for calculating the rank of a number.

Algorithm 1 calculating the rank of a number r (X).

InputX ! (x1; x2; : : : ; xn), p1, p2,. . . , pn 1, pn, wi;j = pi 1 pj 8 : i 6= j & i; j = 1; n, Bi = Pi 1 pi 8 : i = 1; n, $ pi yj(i) % pj

; Parallel processing ; Parallel processing

; Parallel processing $ pn 1 yj(n 1) % pj ; Parallel processing For j = 1, j n, j + + do

If x(j1) + x1 pj Then

r = r Bj ; r = r + rx1 ; Result r

Let's consider an example of how the rank of a number can be calculated using the formulas (22), (23) and (35).

Example. Let the RNS moduli p1 = 2; p2 = 3; p3 = 5 be given, calculate the rank of the number X ! (1; ; 2; 3). (i) RNS range is equal to P = Qin=1 pi = 30. (iii) We calculate the values of constants pi 1 p2 pj

: p3 = It follows from the table 1, that X = j X k = Y ( 2 ) = 3.

p1 p2

Reverse: From the calculations presented in the table 2 it follows that r (X) = 1.

4. Conclusion

In this paper, a new method for calculating the rank of a number in the Residue Number System was presented, and a theorem on the di erence in the ranks of numbers in the Residue Number System was proved. The proposed method allows reducing the amount of necessary calculations and increase the speed of calculating the rank of a number relative to the method for calculating the rank of a number based on the approximate method. To nd the rank of a number in the method for calculating the rank of a number based on the approximate method, it is necessary to calculate n operations with numbers exceeding the modulus value; in the proposed method, it is necessary to calculate n (n 1) operations not exceeding the value of the modulus.

2

Acknowledgements The reported study was funded by RFBR, Sirius University of Science and Technology, JSC Russian Railways and Educational Fund "Talent and success", project number 20-37-51004, and Russian Federation President Grant MK-24.2020.9, and SP3149.2019.5

Y ( 2 )

X ( 2 ) = p2 Y ( 2 ) Y ( 1 ) = X ( 2 ) + y2( 1 )

X ( 2 ) Pn i=1 Pi

p2

X ( 1 ) Pn

i=1 Pi 2 1 =

pi 1 1

X ( 1 )

References

[1] Babenko M , Tchernykh A , Chervyakov N , Kuchukov V , Miranda-Lopez V , Rivera-Rodriguez R , Du Z and Talbi E G 2019 Programming and Computer Software 45 532 { 543

[2] Garner H L 1959 The residue number system Papers presented at the the March 3-5 , 1959 , western joint computer conference pp 146 { 153

[3] Patel R A , Benaissa M and Boussakta S 2007 IEEE Transactions on Computers 56 1484 { 1492

[4] Wang Y 1998 New chinese remainder theorems Conference Record of Thirty-Second Asilomar Conference on Signals, Systems and Computers (Cat. No. 98CH36284) vol 1 (IEEE) pp 165 { 171

[5] Vun C H , Premkumar A B and Zhang W 2013 IEEE Transactions on Circuits and Systems I: Regular Papers 60 2139 { 2152

[6] Tchernykh A , Babenko M , Chervyakov N , Miranda-Lopez V , Avetisyan A , Drozdov A Y , Rivera-Rodriguez R , Radchenko G and Du Z 2020 IEEE Internet of Things Journal 7 10171 { 10188

[7] Bi S and Gross W J 2008 IEEE Transactions on Computers 57 1624 { 1632

[8] Babenko M , Tchernykh A , Chervyakov N , Kuchukov V , Miranda-Lopez V , Rivera-Rodriguez R , Du Z and Talbi E G 2019 Programming and Computer Software 45 532 { 543

[9] Sousa L , Anta~o S and Chaves R 2012 IEEE transactions on very large scale integration (VLSI) systems 21 1945 { 1949

[10] Krasnobayev V , Kuznetsov A , Koshman S and Moroz S 2018 Improved method of determining the alternative set of numbers in residue number system XVIII International Conference on Data Science and Intelligent Analysis of Information (Springer) pp 319 { 328

[11] Chervyakov N , Babenko M , Lyakhov P and Lavrinenko I 2014 Cybernetics and Systems Analysis 50 977 { 984

[12] Chervyakov N , Babenko M , Tchernykh A , Kucherov N , Miranda-Lopez V and Cortes-Mendoza J M 2019 Future Generation Computer Systems 92 1080 { 1092