# A Division Algorithm in a Redundant Residue Number System Using Fractions
## 2 An Approximate Method for Determining the Positional Feature of the Modular Number
### Approximate Method
For an RNS with a 32-bit range, the <<rough estimate>> employs a capacity of \(\widetilde{N}=13\) bits, while the <<clarification>> requires \(N=40\) bits for calculation. The speed of the rough estimate increases 3.08 times. For a 64-bit RNS, the <<rough estimate>> would use a capacity of \(\widetilde{N}=16\) bits, while the <<clarification>> requires \(N=74\) bits. The speed of the rough estimate increases 4.62 times. These results show that, for large ranges, the capacity \(\widetilde{N}\) employed for the rough estimate is significantly lower than the accurate calculation capacity \(N\), which allows significant gains in terms of speed when performing non-modular operations. Figure 1 shows the location of the mentioned intervals for positive and negative numbers in the RNS, and the location of the ambiguity areas, where it is possible to wrongly determine the sign. For the redundant RNS, the numerical range shows a redundancy zone. This allows reducing the number of the checked conditions due to the fact that the sets of the admissible positive numbers and the areas of the erroneous sign determination would no longer intersect (Figure 2). Thus, when speaking of a redundant RNS, determining the sign is reduced to the following tasks. 1. <<Rough estimate>>. If \(0<\left[F(a)\right]_{2-\widetilde{N}}<\frac{1}{2}\), then the number \(a\) is positive. If \(\frac{1}{2}<\left[F(a)\right]_{2-\widetilde{N}}<1-2^{-\widetilde{N}}\rho\), then the number \(a\) is negative. 2. <<Clarification>>. If the number \(a\) is not included in any of the intervals in Step 1, then there is a sign rechecking needed using the \(\left[F(a)\right]_{2^{-N}}\) variables. If \(0<\left[F(a)\right]_{2^{-N}}<\frac{1}{2}\), then the number \(a\) is positive. If \(\frac{1}{2}<\left[F(a)\right]_{2^{-N}}<1\), then the number \(a\) is negative. Let us have a view on employing the approximate method by comparing the numbers in the RNS. **Example 1**. : _We have a system of bases \(p_{1}=2\), \(p_{2}=3\), \(p_{3}=5\), \(p_{4}=7\)._  
Figure 1: Position of ambiguity areas when determining the sign and the intervals for positive and negative numbers for irredundant residue number system (RNS). Figure 2: Position of ambiguity areas when determining the sign and the intervals for positive and negative numbers for redundant RNS. _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\), \(P_{4}=\frac{P}{p_{4}}=30\)._  
The constants \(k_{i}\) used for computing the relative values are:  
\[k_{1}=\frac{\left|\frac{1}{105}\right|_{2}}{2}=\frac{1}{2};\ k_{2}=\frac{ \left|\frac{1}{70}\right|_{3}}{3}=\frac{1}{3};\ k_{3}=\frac{\left|\frac{1}{42} \right|_{5}}{5}=\frac{3}{5};\ k_{4}=\frac{\left|\frac{1}{30}\right|_{7}}{7}= \frac{4}{7}.\]  
For precise operations with relative sizes of numbers in the RNS, it is necessary to use \(N=\left[\log_{2}(P\rho)\right]=12\) characters after the decimal point. For a quick <<rough estimate>>, we will use \(\overline{N}=\left|\log_{2}(N\rho\ln 4)\right|=7\) decimals. The constants \(k_{i}\) rounded up to 7 and 12 bits after the decimal point, are, respectively:  
Seven bits: \(k_{1}=0.1000000\); \(k_{2}=0.0101010\); \(k_{3}=0.1001100\); \(k_{4}=0.1001001\);  
Twelve bits: \(k_{1}=0.10000000000\); \(k_{2}=0.010101010101\); \(k_{3}=0.100110011001\); \(k_{4}=0.100100100100\). The <<rough estimate>> takes checking the conditions \(0<\left[F(a\ )\right]_{2^{-7}}<\frac{1}{2}-2^{-7}\rho\) and \(\frac{1}{2}<\left[F(a\ )\right]_{2^{-7}}<1-2^{-7}\rho\) (Step 1 of the algorithm), which in the binary form will appear as  
1.1. If \(0<\left[F(a)\right]_{2^{-7}}<0.0110011\), then the number \(a\) is positive. 1.2. If \(0,1<\left[F(a\ )\right]_{2^{-7}}<0.1110011\), then the number \(a\) is negative. Let us compare the two numbers \(a=97\)\(nb=8\) presented in the RNS on the bases \(p_{1}\), \(p_{2}\), \(p_{3}\), and \(p_{4}\). Let us define the numbers \(a\) and \(b\) in the RNS as: \(a=(1,\,1,2,\,6)\), \(b=(0,\,2,\,3,\,1)\).