@article{Selianinau_2020, title={An efficient implementation of the Chinese Remainder Theorem in minimally redundant Residue Number System}, volume={21}, url={https://journals.agh.edu.pl/csci/article/view/3616}, DOI={10.7494/csci.2020.21.2.3616}, abstractNote={The Chinese Remainder Theorem (CRT) widely used in many modern computer applications. This paper presents an efficient approach to the calculation of the rank of a number, a principal positional characteristic used in the Residue Number System (RNS). The proposed method does not use large modulo addition operations compared to a straightforward implementation of the CRT algorithm. The rank of a number is equal to a sum of an inexact rank and a two-valued correction factor that only takes on the values 0 or 1. We propose a minimally redundant RNS, which provides low computational complexity of the rank calculation. The effectiveness of the novel method is analyzed concerning conventional non-redundant RNS. Owing to the extension of the residue code, by adding the extra residue modulo 2, the complexity of rank calculation goes down from \(O(k^2)\) to \(O(k)\), where \(k\) equals the number of residues in non-redundant RNS.}, number={2}, journal={Computer Science}, author={Selianinau, Mikhail}, year={2020}, month={Apr.} }