# A Division Algorithm in a Redundant Residue Number System Using Fractions
## 2 An Approximate Method for Determining the Positional Feature of the Modular Number
### Division Algorithm in the RNS  
The algorithm for the \(\frac{a}{b}\) integer division could be described with an iterative scheme, which is performed in two stages. The first stage implies a search for the highest power \(2^{i}\) when approximating the quotient with a binary sequence. The second stage involves clarification of the approximating series. To get a range greater than \(P\), you can select a value \(P^{\prime}=P\cdot p_{n+1}\); thus, it will take expanding the RNS base through adding an extra module. To avoid this base expansion, which is a computationally complex operation, we need to compare not the dividend with the interim divisors but the current results of the iteration (i) with the values of the previous iterations (\(i-1\)). We will repeat the process of doubling the divider as long as the intermediate divider at the \(i\) iteration is below that of the \(i-1\) iteration. This would allow meeting the condition \(0<b<P-1\). The division algorithm can be described with the following rules. A certain rule \(\varphi\) is constructed, which, for each pair of positive integers, \(a\) and \(b\) will assign a certain positive number \(q_{i}\), where \(i\) is the number of the iteration, so that \(a\ -bq_{i}=r_{i}>0\), i.e., \(a\ >bq_{i}\). Then, the division of \(a\) by \(b\) will follow the rule: based on the operation \(\varphi\), each pair of \(a\) and \(b\) will be assigned a corresponding number \(q_{1}=q_{0}\), so that \(a\ -bq_{1}=r_{1}\geq 0\), i.e., \(a\ \geq bq_{1}\). We will take the values \(2^{i}\) as \(q_{i}\) and place them into the memory as the constants \(c_{i}=\left(2^{i}\text{mod}p_{1},\ 2^{i}\text{mod}p_{2},\ \ldots,\ 2^{i}\text{mod}p_{n}\right)\). Given that, the \(i+1\) operation does not depend on the \(i\)-th operation, which allows performing iterations in parallel. Furthermore, in each iteration, there are only two operations performed: multiplication of the constant divisor by \(2^{i}\), and comparison of the obtained values with the dividend. If \(r_{1}\leq b\), then the division is complete; if \(r_{1}\geq b\), then following the rule \(\varphi\), the pair of numbers \((r_{1},\ b)\) will get a \(q_{2}\) assigned, so that \(a\ -bq_{2}=r_{2}\geq 0\), i.e., \(a\ \geq bq_{2}\). If \(r_{2}<b\), then the division is completed, and if \(r_{2}\geq b\), then following the rule \(\varphi\), the pair of numbers \((r_{2},\ b)\) is assigned a \(q_{3}\), so that \(a\ -bq_{3}=r_{3}\geq 0\), etc. Since the consistent application of the operation \(\varphi\) leads to a decreasing sequence of integers \(a\ >r_{1}>r_{2}>\ldots\geq 0\), then the algorithm is implemented in a finite number of steps. Let us assume that at step \(m\) there is a case \(0<bq_{m}\) recorded, which means the end of the division operation. Then, we finally obtain \(a\ \cong(q_{1}+q_{2}+\ldots+q_{m})b+r_{m}\), where the sequence \(q_{1}+q_{2}+\ldots+q_{m}\) is the approximation of the quotient, which may contain some extra \(q_{i}\). Next, we need clarification for the resulting approximating series. In [14] and [16], the idea of the most significant bits for the quotient was introduced for RNS with specialized moduli sets \(\left\{2^{k}+1,2^{k},2^{k}-1\right\}\) and \(\left\{2^{k},2^{k}-1,2^{k}-1\right\}\), while the approach proposed in this paper is extended for a general case. The clarification will start with the higher \(q_{m}\). If \(a>bq_{m}\), then \(q_{m}\) is a member of the approximating series of the resulting quotient. Further, we take \((q_{m}+q_{m-1})\): if \(a\ >b(q_{m}+q_{m-1})\), then \(q_{m-1}\) is put into the line, otherwise, if \(a\ <b(q_{m}+q_{m-1})\), then \(q_{m}\) is excluded from the series, etc. After checking all the \(q_{i}\), the quotient shall be determined by the remaining members of the series. Then, the quotient desired is determined by the expression \(a\ =(q_{m}+q_{m-1}+\ldots+q_{i}+\ldots+q_{1})b+r_{m}\), where  
\[q_{i}=\left\{ \begin{array}{ll}1,\,\text{if}\,(q_{m}+q_{m-1}+\ldots+q_{i})b <a;\\ 0,\,\text{otherwise.}\end{array}