# 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
<<Clarification>>:  
\[\left[F(a\;)\right]_{2^{-12}}=|1\cdot 0.1000000000000+1\cdot 0.010101 010101+10\cdot 0.100110011001+110\cdot 0.100100100100|_{1}=0.011101011111\]Since \(0<[F(a\ )]_{2^{-12}}<0.1\), then the number \(a\) is positive. \[ \begin{array}{l}[F(b)]_{2^{-12}}=|0\cdot 0.100000000000+1\cdot 0.010101010101+10 \cdot 0.100110011001+110\cdot 0.100100100100|_{1}=\\ =0.111101011111\end{array} \]  
Since \(0.1<[F(b)]_{2^{-12}}<1\), then the number \(b\) is negative. The numbers \(a\) and have opposite signs, so the quotient sign will be negative. In order to find the absolute value of the quotient, we will divide \(a\) by \(-b=(0,\ 0,\ 0,\ 0)-(0,\ 1,\ 2,\ 6)=(0,\ 2,\ 3,\ 1)\) following the algorithm as specified above. The relative values of the dividend \(a\) and the divisor \(-b\) with full accuracy of the calculations \(N\) are:  
\[[F(a\ )]_{2^{-12}}=0.01110101111;\ [F(-b)]_{2^{-12}}=0.000010011001.\]  
Shifting the fractional part of the divisor \(-b\) to the left, step by step, we determine that a change in the first fractional bit after the decimal point occurs at the fourth shift. Thus, the approximation series can include only the values \(2^{0}\), \(2^{1}\), \(2^{2}\), and \(2^{3}\), which, in the RNS, have the following representation:  
\[q_{0}=2^{0}=(1,\ 1,\ 1,\ 1);\ q_{1}=2^{1}=(0,\ 2,\ 2,\ 2);\ q_{2}=2^{2}=(0,\ 1,\ 4,\ 4);\ q_{3}=2^{3}=(0,\ 2,\ 3,\ 1).\]  
These values develop the approximation sequence of the quotient, which is to be clarified later on. For a more accurate approximation sequence, we will subtract from the fraction \([F(a\ )]_{2^{-12}}\) of the dividend the fraction of the divisor \([F(-b)]_{2^{-12}}\) that has been shifted three ranks to the left (i.e., multiplied by \(2^{3}\)):  
\[\Delta_{1}=[F(a\ )]_{2^{-12}}-2^{3}\cdot[F(-b)]_{2^{-12}}=0.011101011111-0.010 011001=0.001010010111.\]  
Since \(\Delta_{1}>0\), then we will leave \(2^{3}\) in the approximation sequence, while the value \(\Delta_{1}\) will be used for further calculations. We subtract from \(\Delta_{1}\) the fraction \([F(-b)]_{2^{-12}}\) of the divisor shifted left two ranks:  
\[\Delta_{2}=\Delta_{1}-2^{2}\cdot[F(-b)]_{2^{-12}}=0.00101001011-0.0010011001= 0.000000110011.\]  
Since \(\Delta_{2}>0\), then we leave \(2^{2}\) in the approximation sequence, while the value \(\Delta_{2}\) will be used for further calculations. We subtract from \(\Delta_{2}\) the fraction \([F(-b)]_{2^{-12}}\) of the divisor shifted left one rank:  
\[\Delta_{3}=\Delta_{2}-2^{1}\cdot[F(-b)]_{2^{-12}}=0.000000110011-0.00010011001 =1.111100000001\]  
The appearance of \(1\) in the sign rank indicates that \(\Delta_{3}<0\), therefore \(2^{1}\) is excluded from the approximation sequence, and \(\Delta_{3}\) is not to be used further (continue using \(\Delta_{2}\)). We subtract from \(\Delta_{2}\) the fraction \([F(-b)]_{2^{-12}}\) of the divisor (no shift applied):  
\[\Delta_{4}=\Delta_{2}-2^{01}\cdot[F(-b)]_{2^{-12}}=0.000000110011-0.000010011001 =1.111110011010.\]  
The appearance of \(1\) in the sign rank indicates that \(\Delta_{4}<0\), so \(2^{0}\) is excluded from the approximation sequence. Here, the process of clarifying the approximation sequence comes to an end. To determine the quotient, we need to add the remaining members of the approximation sequence. In this example, the remaining members were the following ones: \(q_{3}=2^{3}=(0,\ 2,\ 3,\ 1)\) and \(q_{2}=2^{2}=(0,\ 1,\ 4,\ 4)\). Then the absolute value of the quotient is to be determined through summing the members of the sequence:  
\[\left\|\frac{a}{b}\right\|=(0,\ 2,\ 3,\ 1)+(0,\ 1,\ 4,\ 4)=(0,\ 0,\ 2,\ 5)=12.\]In view of the sign, we finally obtain \(\left\lfloor\frac{a}{b}\right\rfloor=-12\). Figure 3 demonstrates the scheme of positional characteristics calculation based on CRTf for a number \(X=\left\{x_{1},x_{2},\ldots,x_{n}\right\}\). A bit's width of values \(x_{i}\) is equal to \(\left\lceil\log_{2}p_{i}\right\rceil\), \(i=1,\ 2,\ \ldots\,\ n\).