COMPUTER SOFTWARE AND COMPUTING EQUIPMENT

On an algorithm for number comparison in the residue number system

K. S. Isupov

Vyatka State University

Abstract: Modular arithmetic (the representation of numbers in residue number systems) has an internal data parallelism and therefore is a promising tool for the efficient organization of high-precision computations. However, due to the high complexity of non-modular operations, such as a comparison, sign determination, dynamic range overflow control, scaling and division, area of effective application of a modular processing is bounded to a small enough class of specific problems. In this paper, the ways of evaluation of positional magnitude number in the modular representation is reviewed. A new interval-positional characteristic of modular arithmetic, providing an obtainment of a reliable approximation of relative magnitude of the number by means of $O(n)$ floating-point operations in the serial case and by means of $O(\log n)$ operations if a parallel algorithm is used, where $n$ is a count of residue number system modules, is presented. A new algorithm for comparison of numbers in the residue number system based on the calculation and the analysis of interval-positional characteristics is developed. The proposed algorithm does not require a storage in the memory of the large-size lookup tables; it provides a correct comparison of the result and is characterized with high performance. The performed analysis of the computational complexity shows that, depending on the input data combination, speedup of the proposed algorithm can reach $0.18n$ times in comparison with the similar algorithm based on the conversion of numbers in the mixed radix system. The questions of interval-positional characteristic precision are also discussed. A new fast algorithm that helps in limited-bit machine arithmetic calculate an interval-positional characteristic with relative error less than a priori given bound, is reviewed. The recommendations for the practical application of the obtained results are formulated.

Keywords: residue number system, non-modular operation, number comparison, relative magnitude of the number, interval-positional approximation, mixed radix system.

UDC: 004.272.2

Received: 15.05.2014