# A Division Algorithm in a Redundant Residue Number System Using Fractions
## 2 An Approximate Method for Determining the Positional Feature of the Modular Number
### Clarification of the Quotient's Approximating Sequence  
Step 5. From the memory, we select the constant \(2^{j}\) (the highest power of the series) and multiply it by the divisor. The value \(2^{j}F(b)\) will be compared with the dividend \(F(a)\) using the approximate method of number comparison in the RNS. The constants \(2^{j}\), \(1\leq j\leq\log_{2}P\) are previously placed in the memory \(V\); the counter \(j\) and the quotient \(Q\) are set on <<\(b\)>>. The outputs of the counter are address inputs in the memory \(V\). Step 6. Calculate the \(\Delta_{1}=F(a)-F_{1}(b)\). If the sign bit \(\Delta_{1}\) the value is <<\(b\)>>, then the corresponding power series is discarded; if the value is <<\(b\)>>, then to the quotient adder we add the value of the sequence members with the same degree, i.e., \(2^{j}\text{mod}p_{i}\), \(1\leq i\leq n\), \(0\leq j\leq N\). Step 7. Check the sequence member of the \(2^{j-1}\) degree through a shift to the right and comparison. Compare \(\Delta_{1}\) and \(2^{j-1}b\). If \(\Delta_{1}<2^{j-1}b\), then the corresponding power series is discarded; if \(\Delta_{1}>2^{j-1}b\), then to the quotient adder we add the value of the sequence members with the same degree, i.e., \(2^{j-1}\text{mod}p_{i}\;n\Delta_{2}=\Delta_{1}-2^{j-1}b\). Step 8. Similarly, check all the remaining sequence members up to degree zero. The last \(\Delta_{i}=R=\Delta_{i-1}-F_{i-1}\), i.e., \(0\leq R<b\) will be the remainder of \(a\) divided by \(b\). The quotient \(Q\) will be the sum of all the \(2^{j}\) needed for developing the quotient, which was accumulated in the adder with the sign as defined in the second step. The algorithm terminates. The performance of the modified algorithm could be further shown with the example below. **Example 2**. : _Find the quotient \(Q=\frac{a}{b}\) of dividing \(a\;=97\) by \(b=-8\) in an RNS with bases \(p_{1}=2\), \(p_{2}=3\), \(p_{3}=5\), \(p_{4}=7\). Then \(P=2\cdot 3\cdot 5\cdot 7=210\), \(\rho=2+3+5+7-4=13\), \(P_{1}=\frac{P}{p_{1}}=105\), \(P_{2}=\frac{P}{p_{2}}=70\), \(P_{3}=\frac{P}{p_{3}}=42\), and \(P_{4}=\frac{P}{p_{4}}=30\)._  
The constants \(k_{i}\) used for calculation of the relative values are:  
\[k_{1}=\frac{|\frac{1}{105}|_{2}}{2}=\frac{1}{2};\;k_{2}=\frac{|\frac{1}{70}|_ {3}}{3}=\frac{1}{3};\;k_{3}=\frac{|\frac{1}{42}|_{5}}{5}=\frac{3}{5};\;k_{4}= \frac{|\frac{13}{30}|_{7}}{7}=\frac{4}{7}.\]  
For a quick <<rough estimate>>, we will use \(\widetilde{N}=\left\lfloor\log_{2}(N\rho\ln 4)\right\rfloor=7\) characters after the decimal point. The constants \(k_{i}\) rounded up to 7 bits after the decimal point are:  
Seven bits: \(k_{1}=0.1000000;k_{2}=0.0101010;k_{3}=0.1001100;k_{4}=0.1001001\). Precise operations with relative values of the numbers in the RNS take \(N=\left\lceil\log_{2}(P\rho)\right\rceil=12\) characters after the decimal point. The constants \(k_{i}\) rounded up to 12 binary bits after the decimal point are:  
\[ \begin{array}{ll}k_{1}=0.100000000000;&k_{2}=0.010101010101;\;k_{3}=0.100110 011001;\\ &k_{4}=0.100100100100.\end{array} \]  
Now, we shall represent the \(a\;ub\) numbers in the RNS:  
\[a_{10}=97\rightarrow\;(1,\;1,\;2,\;6)_{RNS},\]  
\[b_{10}=-8\;\rightarrow\;(0,\;1,\;2,\;6)_{RNS}.\]  
Determine the signs of the numbers \(a\) and \(b\). A <<rough estimate>> (binary):  
\[\left[F(a\;)\right]_{2^{-7}}=|1\cdot 0.1000000+1\cdot 0.0101010+10\cdot 0.1001100+110 \cdot 0.1001001|_{1}=0.0111000.\]  
Since \(\left[F(a\;)\right]_{2^{-7}}\) misses any one of the intervals (\(0\); \(0.0110011\)), (\(0.1\); \(0.1110011\)) as set forth in Example 1 will take a clarifying iteration:  
\[\left[F(b)\right]_{2^{-7}}=|0\cdot 0.1000000+1\cdot 0.0101010+10\cdot 0.1001100+110 \cdot 0.1001001|_{1}=0.1111000\]  
\(\left[F(b)\right]_{2^{-7}}\), too, misses all the intervals (\(0\); \(0.0110011\)), (\(0.1\); \(0.1110011\)) as set forth in Example 1, so it will take another clarifying iteration.