# A Division Algorithm in a Redundant Residue Number System Using Fractions
## 1 Introduction  
The residue number system (RNS) has attracted many researchers as a basis for computing, and the interest taken in it has increased dramatically over the latest decade, which could be seen from the large number of papers focusing on the practical application of RNS in digital signal processing, image processing systems, cryptographic systems, quantum automated machines, neural computers systems, massive concurrency of operations, cloud computing, etc. [1; 2; 3; 4; 5; 6; 7]. RNS, if compared to other scales of notation, offers the advantage of rapid addition and multiplication, which causes stirs of interest in the RNS in areas requiring large amounts of computation. However, some operations, such as comparison and division of numbers, are very complicated in the RNS. Finding faster division algorithms would allow detecting more promising new areas to apply RNS. The known RNS division algorithms [8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22; 23] can be divided into two classes: based on the comparison of numbers, and based on the subtraction. The algorithm for integer division operates similarly to a conventional binary division proposed in [1; 2]. This algorithm and its modifications have a major drawback, namely that each iteration requires a comparison of numbers. The algorithm without these drawbacks, as proposed in [1; 2], is based on replacing the divider by an approximate value, which may be the product of one or several RNS modules. The algorithm provides a correct result for the condition \(b\leq\overline{b}<2b\), where \(b\) is an actual divider and \(\overline{b}\) is an approximation of \(b\). It is easy to see that this condition cannot be satisfied for all moduli sets (for example: \(p_{1}=9\), \(p_{2}=11\), \(b=4\)). The main disadvantages of this algorithm are the necessity of mixed radix conversion (MRC) and scaling operations use, and special logic and tables for determining the approximate divider. There have been proposed several algorithms for solving the problem of division based on a comparison of numbers and methods of determining the sign, which can be classified as follows: [8; 10; 15] using MRC, [9] to formulate the problem in terms of determining the even numbers, and [11] using the base extension operation in iterations. All the proposed algorithms, however, have the disadvantage of long computation time and high hardware costs due to the use of MRC, Chinese remainder theorem (CRT), and other costly operations. In [12; 13; 14; 16], a high-speed division algorithm is presented, which uses the comparison of higher degrees of dividend and divisor instead of using the MRC and CRT for the division of modular numbers. The time complexity and hardware costs in these algorithms are smaller than other algorithms, although this algorithm contains redundant stages. To speed up the calculation of the current quotients, [PERSON] and [PERSON] suggested a division algorithm based on parity checking, in which the quotient calculation occurs two times faster than the algorithms [14; 16]. However, the calculation of the higher powers of two is time-consuming in the RNS, which are carried out in each cycle. The known algorithm of division in the RNS format, in addition to the RNS moduli set, also uses a replacement module system, which is an auxiliary to preserve the dividend and divisor residues. Presented in the RNS dividend and divisor are converted into a variety of RNS presentations with the various modules of the system [18]. Using two moduli sets of RNS leads to a large redundancy and the necessity for direct and reverse conversion from moduli set to the auxiliary and back for the division operation, which drastically reduces its speed. A fast algorithm for the division based on the use of the index over the Galois field transformation \(GF(p)\) is proposed in [18], which was simply implemented using LUTs (Look-Up Table). However, this algorithm is effective when processing data no more than 6-10 bits and when a modulus is a prime number.