# 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
In case of accurate comparison, which is widely used in the division of numbers, you need to calculate a value that is equivalent to the conversion of the RNS into the positional notation. Rounding the \(F(a)\) value will inevitably result in an error. Let us denote \(\rho=-n+\sum\limits_{i=1}^{n}p_{i}\). Work [22] shows that it is necessary to use \(N=\left\lceil\log_{2}(P\rho)\right\rceil\) bits after the decimal point when rounding the value \(F(a)\), so that the resulting error has no effect on the accuracy of calculations. In other words, there is established a one-to-one correspondence between the set of numbers represented in the RNS and the plurality of \(\left[F(a)\right]_{2^{-N}}\) values. Using the variables \(\left[F(a)\right]_{2^{-N}}\) in calculations, in terms of algorithmic complexity, is equivalent to applying the inverse transformation from the RNS into the positional notation using the CRT. This method is slow and therefore, in practice, the use of calculations with the values \(\left[F(a)\right]_{2^{-N}}\) is not rational. In [22], it is shown that it is possible to use the values \(\left[F(a)\right]_{2^{-\widetilde{N}}}\), where \(\widetilde{N}<N\), for operations of determining the number sign in the RNS. The point of this approach is based on the fact that when determining the sign there is no need to know the exact value of the number, and it is just enough to know about the range within which the number tested falls. The algorithm for determining the sign of the number serves the basis for number comparison algorithms. Determining the sign of the number in the RNS using the values \(\left[F(a)\right]_{2^{-t}}\), takes the following operations:  
1. \(\ast\)Rough estimate\(\Rightarrow\). At this stage, the value \(\left[F(a)\right]_{2^{-\widetilde{N}}}\), \(\widetilde{N}<N\) is used. If \(0<\left[F(a)\right]_{2^{-\widetilde{N}}}<\frac{1}{2}-2^{-\widetilde{N}}\rho\), 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. \(\ast\)Clarification\(\Rightarrow\). If the number \(a\) falls into none of the intervals as indicated in Step 1, then a rechecking of the number is needed with maximum precision calculation regarding the \(\left[F(a)\right]_{2^{-N}}\) values. 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. The speed of the algorithm at the stage of the \(\ast\)rough estimate\(\Rightarrow\) depends on how little the value \(\widetilde{N}\) is compared to \(N\). However, if \(\widetilde{N}\) is taken as too little, then the intervals in Step 1 may be so small that the algorithm for numerous numbers in the RNS would require the use of the \(\ast\)clarification\(\Rightarrow\) stage, while the benefit of using a small capacity at the \(\ast\)rough estimate\(\Rightarrow\) stage would be dismissed completely. For example, in [13], it is proposed to use the case when \(\widetilde{N}=4\) that is usually too small for practice. Instead, we suggest using an estimation from [22], which shows that the optimal speed of the algorithm is achieved with \(\widetilde{N}\approx\log_{2}(N\rho\ln 4)\). Here below comes a comparison of the \(\widetilde{N}\) and \(N\) capacities for the RNS, where the ranges of 16, 32, and 64 bits are implemented. 1. Sixteen bits. RNS modules 7, 17, 19, 29. \[P=65569;\;\rho=68;\;N=23;\;\widetilde{N}=11.\]  
2. Thirty-two bits. RNS modules 2, 3, 5, 11, 13, 19, 23, 29, 79. \[P=4295006430;\;\rho=175;\;N=40;\;\widetilde{N}=13.\]  
3. Sixty-four bits. RNS modules 2, 11, 17, 19, 23, 31, 41, 53, 59, 61, 71, 79, 83. \[P=18446748995286100082;\;\rho=537;\;N=74;\;\widetilde{N}=16.\]  
Thus, with an RNS of a 16-bit range, the \(\ast\)rough estimate\(\Rightarrow\) is done using the values with a capacity of \(\widetilde{N}=11\) bits, while the \(\ast\)clarification\(\Rightarrow\) takes place at the \(N=23\) bit precision. The speed of the rough estimate goes up by 2.09 times.