1. Field of the Invention
The present invention relates to a residue number system (RNS) arithmetic operating system, a scaling operator, a scaling operation method and a program and a recording medium of the same. More specifically, the invention relates to the RNS arithmetic operating system, the scaling operator, the scaling operation method and the program and recording medium of the same for efficiently carrying out scaling operation of numbers represented by RNS.
2. Related Art
Conventionally, numerical arithmetic operation by means digital circuits has been realized by logical circuits based on binary number. There has been also proposed a numerical arithmetic operation method based on Residue Number System (RNS) lately as disclosed in B. Parhami, Computer Arithmetic, Oxford University Press, 2000, pp. 54-72. It has been known that additions, subtractions and multiplications may be carried at high speed by the RNS more than arithmetic operations by means of the conventional binary number, by reasons described below.
In additions in binary number, a carry signal is generated from arithmetic operation of each bit and propagates from the LSB side to the MSB side. Therefore, it is unable to determine a calculation result of i-th digit until when the carry signal of the i-th bit reaches to that digit.
Accordingly, a value of delay increases in proportional to a number of bits of operand to be operated. Meanwhile, the arithmetic operation in the RNS may be carried out at high speed because calculation may be carried out independently and in parallel in each residue digit and its operation speed is not dependent on a number of bits to be computed.
The RNS represents one number X by a set of N residue numbers (residues).X=(x0,x1,x2, . . . , xN-1)  (1-1)
In Equation (1-1), xi=X mod mi (also represented as xi=|X|mi), which is a residue obtained by dividing X by i-th modulus mi. Further, xi is called as a residue digit or as a residue obtained with respect to the modulus mi. Here, mod is an abbreviation of modulo and means that the following Equation (1-2) holds.X=pmi+xi  (1-2)
Here, p is a quotient obtained by dividing X by mi. At this time, X is congruent with xi with respect to the modulus mi and may be represented by the following Equation by using a congruence expression.X≡xi mod mi  (1-3)
When N moduli mi (i=0, 1, 2, . . . , N−1) are relatively prime, all numbers X in the following range may be represented by a unique set of N residue numbers. At this time, {mi, m2, . . . , MN-1} is called as a modulus set.
                              0          ≤          X          <                                    ∏                              i                =                0                                            N                -                1                                      ⁢                          m              i                                      =        M                            (                  1          ⁢                      -                    ⁢          4                )            
When a residue representation using the modulus set {m1, m2, . . . , mN-1}=(8, 7, 5, 3) is considered for example, this RNS can represent integers of M=8×7×5×3=840. For example, (0, 0, 0, 0)RNS is 0 or 840 or 1680, (1, 1, 1, 1)RNS is 1 or 841 or 1681, (0, 1, 3, 2)RNS is 8 or 848 or 1688 and (0, 1, 4, 1)RNS is 64 or 904 or 1744. Then, in case of the modulus set (8, 7, 5, 3), a number of bits necessary for representing each residue digit is
=11 bits.
Additions, subtractions and multiplications may be realized by independently operating each residue digit in the RNS, so that no information needs to be propagated among the residue digits. That is, the following theorem holds.
(Theorem of RNS Additions, Subtractions and Multiplications)
When an operator “O” is an operator for representing additions, subtractions or multiplications, moduli of RNS are {m1, m2, . . . , mN-1} and operands are A (a1, a2, . . . , aN-1) and B ((b1, b2, . . . , bN-1), Z=AOB may be realized by operating the residue digits of the operands to each modulus.|Y|mi=yi=|ai·bi|mi  (1-5)
Here, the left side is the residue of Y obtained with respect to mi. The arithmetic operation of Equation (1-5) is also called as residue addition, residue subtraction or residue multiplication. The theorem of RNS additions, subtractions and multiplications may be proved as follows.
(Proof of Theorem of RNS Additions, Subtractions and Multiplications)
The following equation (1-6) holds from the definition of numerical representation of the RNS.A=pimi+ai, B=qimi+bi  (1-6)
Here, pi is a quotient obtained by dividing A by the modulus mi and qi is a quotient obtained by dividing B by the modulus mi.
The following Equation (1-7) holds in the additions and subtractions.
                                                                                                            Y                                                                    m                  i                                            =                                                                                      A                    ±                    B                                                                                      m                  i                                                                                                        =                                                                                                                                    p                        i                                            ⁢                                              m                        i                                                              +                                                                  a                        i                                            ±                                                                        q                          i                                                ⁢                                                  m                          i                                                                                      +                                          b                      i                                                                                        ⁢                                  m                  i                                                                                                        =                                                                                                                                    (                                                                              p                            i                                                    +                                                      q                            i                                                                          )                                            ⁢                                              m                        i                                                              +                                                                  a                        i                                            ±                                              b                        i                                                                                                              ⁢                                  m                  i                                                                                        (                  1          ⁢                      -                    ⁢          7                )            
Here, the following Equation (1-8) holds from (pi+qi)mi≡0.|Y|mi=|ai±bi|mi  (1-8)
Meanwhile, the following Equation (1-9) holds in multiplications.
                                                                                                            Y                                                                    m                  i                                            =                            ⁢                                                                  AB                                                                    m                  i                                                                                                        =                            ⁢                                                                                                            (                                                                                                    p                            i                                                    ⁢                                                      m                            i                                                                          +                                                  a                          i                                                                    )                                        ⁢                                          (                                                                                                    q                            i                                                    ⁢                                                      m                            i                                                                          +                                                  b                          i                                                                    )                                                                                                          m                  i                                                                                                        =                            ⁢                                                                                                                                    (                                                                                                            p                              i                                                        ⁢                                                          q                              i                                                        ⁢                                                          m                              i                                                                                +                                                                                    p                              i                                                        ⁢                                                          b                              i                                                                                +                                                                                    q                              i                                                        ⁢                                                          a                              i                                                                                                      )                                            ⁢                                              m                        i                                                              +                                                                  a                        i                                            ⁢                                              b                        i                                                                                                                                m                  i                                                                                        (                  1          ⁢                      -                    ⁢          9                )            
Here, the following Equation (1-10) holds from (piqimi+qiai)mi≡0.|Y|mi=|aibi|mi  (1-10)
It will be seen from the above Equations (1-8) and (1-10) that each residue digit of Y may be calculated by carrying out arithmetic operation of each residue digit of A and B. Accordingly, it is proved that the theorem of Equation (1-5) holds.
From the theorem of RNS additions, subtractions and multiplications, it becomes possible to realize additions, subtractions and multiplications in the RNS by providing a residue arithmetic logic unit (residue ALU) for carrying out the arithmetic operation with respect to the pertinent residue digit per residue digit corresponding to the two inputted operands A and B and to the operation result Y to be outputted. It also allows calculation of a certain residue digit to be carried out independently from calculation of the other residue digits. The arithmetic operation by means of the residue ALU corresponding to each residue digit may be carried out at higher speed because the delay caused by the carry-propagation is limited to that of a number of bits of the residue digit.
In order to increase the speed of the numerical arithmetic operation using the RNS, it is necessary to convert systems from the binary or decimal system to the RNS (Binary-to-Residue B/R) converter) and to convert from the RNS to the binary or decimal system (Residue-to-Binary (R/B) converter). While the B/R converter may be realized relatively easily, several methods for realizing the R/B converter are being discussed.
For the R/B converter, one using Chinese Remainder Theorem is used in general. A case of converting Y=(y0, y1, y2, Y3)=(5, 3, 4, 2) into the decimal system when a modulus set {m0, m1, m2, m3}={8, 7, 5, 3} will be exemplified below.
(5, 3, 4, 2) may be reduced as shown in the following Equation (1-11) from the theorem of RNS additions, subtractions and multiplications shown in Equation (1-5) and then Equation (1-12) may be obtained.(5,0,0,0)+(0,3,0,0)+(0,0,4,0)+(0,0,0,2)  (1-11)5×(1,0,0,0)+3×(0,1,0,0)+4×(0,0,1,0)+2×(0,0,0,1)  (1-12)
An arbitrary residue representation (y0, y1, y2, Y3) may be converted into the decimal representation by using the following Equation (1-13) by thus finding the decimal representation corresponding to (1,0,0,0), (0,1,0,0), (0,0,1,0) and (0,0,0,1) in advance.y0×(1,0,0,0)+y1×(0,1,0,0)+y2×(0,0,1,0)+y3×(0,0,0,1)  (1-13)
Here, (1, 0, 0, 0) is a number whose residue obtained with respect to modulus 8(=m0) is 1 mid whose residue obtained with respect to a modulus subset {7, 5, 3}={, m1, m2, m3} is 0. The latter condition may be met by calculating (1, 0, 0, 0) under the condition that it is a least common multiple of m1, m2, m3. These conditions may be represented by the following Equation (1-14).a) (1,0,0,0)mod m0=1,b) (1,0,0,0)=β0·m1·m2·m3  (1-14)
Here, β0 is a natural number. Then, if m1, m2, m3 are relatively prime, the conditions of a) and b) may be rewritten to the following equation (1-15) from Equation (1-4).β0·(M/m0)mod m0=1  (1-15)
The decimal notation of (1, 0, 0, 0) is given by finding the above natural number β0. The following Equation (1-16) shows the decimal notation of (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0) and (0, 0, 0, 1) obtained with respect to the RNS of {8, 7, 5, 3}.m0=8:M/m0=105, β0=1(1≡105 mod 8)∴(1,0,0,0)=105m1=7:M/m1=120, β1=1(1≡120 mod 7)∴(0,1,0,0)=120m2=5:M/m2=168, β2=2(1≡168×2 mod 5)∴(0,0,1,0)=336m3=3:M/m3=280, β3=1(1≡280 mod 3)∴(0,0,0,1)=280.  (1-16)
Equation (1-16) converts the numbers (5, 3, 4, 2) represented by the RNS of {8, 7, 5, 3} into the decimal system of 5×105+3×120+4×336+2×280=2117. However, because the number represented by this RNS is 0≦Y<M=840, Y=|2117|M=437.
The Chinese remainder theorem is led by the following Equation in general.
                                                                        (                                                      y                    0                                    ,                                      y                    1                                    ,                  …                  ⁢                                                                          ,                                      y                                          N                      -                      1                                                                      )                            =                            ⁢                                                                    y                    0                                    ⁡                                      (                                          1                      ,                      0                      ,                      0                      ,                      …                      ⁢                                                                                          ,                      0                                        )                                                  +                                                                                                      ⁢                                                                    y                    1                                    ⁡                                      (                                          0                      ,                      1                      ,                      0                      ,                      …                      ⁢                                                                                          ,                      0                                        )                                                  +                …                ⁢                                                                  +                                                                                                      ⁢                                                y                                      N                    -                    1                                                  ⁡                                  (                                      0                    ,                    0                    ,                    0                    ,                    …                    ⁢                                                                                  ,                    1                                    )                                                                                                        =                            ⁢                                                                                                          y                      0                                        ⁡                                          (                                                                        β                          0                                                ·                                                  M                                                      m                            0                                                                                              )                                                        +                                                            y                      i                                        ⁡                                          (                                                                        β                          1                                                ·                                                  M                                                      m                            1                                                                                              )                                                        +                  …                  ⁢                                                                          +                                                                                                                                        ⁢                                                      y                                          N                      -                      1                                                        ⁡                                      (                                                                  β                                                  N                          -                          1                                                                    ·                                              M                                                  m                                                      N                            -                            1                                                                                                                )                                                                              M                                                                          =                            ⁢                                                                                                            ∑                                              i                        =                        0                                                                    N                        -                        1                                                              ⁢                                          (                                                                        y                          i                                                ·                                                  β                          i                                                ·                                                  M                                                      m                            1                                                                                              )                                                                                        M                                                                        (                  1          ⁢                      -                    ⁢          17                )            
The use of the RNS allows additions, subtractions and multiplications to be calculated at high speed. However, it has had a problem that due to scaling operation described below, its speed is not faster than the speed of calculation of additions, subtractions and multiplications carried out by means of binary system.
When multiplication of n bits×n bits is carried out by means of binary system, its multiplication result is (2n) bits. If multiplication is to be carried out only once like (514)×(237) for example, it will do by just outputting a multiplication result of (2n) bits as it is for the n bits inputted.
However, an output number of bits increases if multiplication is repeated like (514)×(237)× . . . ×(353) for example. When decimal numbers of ( 15/16)×( 15/16) is calculated for example, it results in ( 225/256). However, when output bits is only four, a part of the calculation result is truncated, outputting the same n bits with the number of bits inputted as the calculation result. It is equivalent to a process of shifting to right by n bits. In this example, ( 15/16)×( 15/16)−( 225/256) is shifted by 4 bits to output ( 14/16) as the multiplication result. This carry-matching process is called as Scaling and is used in carry-matching mantissa part in floating-point multiplication for example.
This scaling process may be applied to binary number just by carrying out the bit-shift process or just by masking unnecessary bits because weighting has been implemented corresponding to each digit of binary number. That is, it requires only shifting time corresponding to n bits. However, it is unable to realize the scaling to numbers represented by the RNS by the bit shift operation. For example, when multiplication of (5, 3, 4, 2)×(3, 2, 4, 2) (=437×779 dec) is carried out in the RNS of {8, 7, 5, 3} for example, it results in 340,423 dec. This RNS can represent only a number up to 839 in maximum. Accordingly, it is necessary to scale by M=840 in the RNS of {8, 7, 5, 3} so that the multiplication result becomes 405. However, (5, 3, 4, 2)×(3, 2, 4, 2)=(7, 6, 1, 1)RNS{8,7,5,3} and it is unable to scale to 405=(5, 6, 0, 0) as it is.
It is conceivable of utilizing the Chinese remainder theorem in order to carry out scaling in the RNS. That is, the multiplication result (7, 6, 1, 1) is converted into a binary number of (1010011000111000111) and this result is scaled by the means of the bit-shift described above to obtain (101001100). Then, it is converted again into the RNS to obtain (5, 6, 0, 0). However, it takes time for the calculation because the Chinese remainder theorem is involved in multiplication of each residue digit yi and the constant bi·(M/mi) as shown in Equation (1-17). The merit of multiplication in the RNS (increase of calculation speed) is lost if the Chinese remainder theorem is used to convert the RNS into the binary system and to scale per multiplication in carrying out a number calculating process that frequently uses multiplications.