residue number system

{{multiple issues|

{{missing information|many aspects of the subject (see the talk page)|date=July 2018}}

}}

A residue number system or residue numeral system (RNS) is a numeral system representing integers by their values modulo several pairwise coprime integers called the moduli. This representation is allowed by the Chinese remainder theorem, which asserts that, if {{mvar|M}} is the product of the moduli, there is, in an interval of length {{mvar|M}}, exactly one integer having any given set of modular values.

Using a residue numeral system for arithmetic operations is also called multi-modular arithmetic.

Multi-modular arithmetic is widely used for computation with large integers, typically in linear algebra, because it provides faster computation than with the usual numeral systems, even when the time for converting between numeral systems is taken into account. Other applications of multi-modular arithmetic include polynomial greatest common divisor, Gröbner basis computation and cryptography.

Definition

A residue numeral system is defined by a set of {{mvar|k}} integers

: $\{ m_1, m_2, m_3,\ldots, m_k\},$

called the moduli, which are generally supposed to be pairwise coprime (that is, any two of them have a greatest common divisor equal to one). Residue number systems have been defined for non-coprime moduli, but are not commonly used because of worse properties.

An integer {{mvar|x}} is represented in the residue numeral system by the family of its remainders (indexed by the moduli of the indexes of the moduli)

: $\{ x_1,x_2,x_3,\ldots,x_k \}$

under Euclidean division by the moduli. That is

: $x_i = x \operatorname{mod}m_i,$

and

: $0\le x_i$

for every {{mvar|i}}

Let {{mvar|M}} be the product of all the $m_i$ . Two integers whose difference is a multiple of {{mvar|M}} have the same representation in the residue numeral system defined by the {{math|m_i}}s. More precisely, the Chinese remainder theorem asserts that each of the {{mvar|M}} different sets of possible residues represents exactly one residue class modulo {{mvar|M}}. That is, each set of residues represents exactly one integer $X$ in the interval $0,\dots,M-1$ . For signed numbers, the dynamic range is ${-\lfloor M/2 \rfloor} \le X \le \lfloor (M-1)/2 \rfloor$

(when $M$ is even, generally an extra negative value is represented).{{Cite journal|last1=Hung|first1=C.Y.|last2=Parhami|first2=B.|date=1994-02-01|title=An approximate sign detection method for residue numbers and its application to RNS division|url=https://core.ac.uk/download/pdf/81980039.pdf|journal=Computers & Mathematics with Applications|language=en|volume=27|issue=4|pages=23–35|doi=10.1016/0898-1221(94)90052-3}}

Arithmetic operations

For adding, subtracting and multiplying numbers represented in a residue number system, it suffices to perform the same modular operation on each pair of residues. More precisely, if

: $[m_1, \ldots, m_k]$

is the list of moduli, the sum of the integers {{mvar|x}} and {{mvar|y}}, respectively represented by the residues $[x_1,\ldots, x_k]$ and $[y_1,\ldots, y_k],$ is the integer {{mvar|z}} represented by $[z_1,\ldots, z_k],$ such that

: $z_i= (x_i+y_i)\operatorname{mod} m_i,$

for {{math|1=i = 1, ..., k}} (as usual, mod denotes the modulo operation consisting of taking the remainder of the Euclidean division by the right operand). Subtraction and multiplication are defined similarly.

For a succession of operations, it is not necessary to apply the modulo operation at each step. It may be applied at the end of the computation, or, during the computation, for avoiding overflow of hardware operations.

However, operations such as magnitude comparison, sign computation, overflow detection, scaling, and division are difficult to perform in a residue number system.

=Comparison=

If two integers are equal, then all their residues are equal. Conversely, if all residues are equal, then the two integers are equal or differ by a multiple of {{mvar|M}}. It follows that testing equality is easy.

At the opposite, testing inequalities ({{math|x < y}}) is difficult and, usually, requires to convert integers to the standard representation. As a consequence, this representation of numbers is not suitable for algorithms using inequality tests, such as Euclidean division and Euclidean algorithm.

=Division=

Division in residue numeral systems is problematic. On the other hand, if $B$ is coprime with $M$ (that is $b_i\not =0$ ) then

: $C=A\cdot B^{-1} \mod M$

can be easily calculated by

: $c_i=a_i \cdot b_i^{-1} \mod m_i,$

where $B^{-1}$ is multiplicative inverse of $B$ modulo $M$ , and $b_i^{-1}$ is multiplicative inverse of $b_i$ modulo $m_i$ .

Applications

RNS have applications in the field of digital computer arithmetic. By decomposing in this a large integer into a set of smaller integers, a large calculation can be performed as a series of smaller calculations that can be performed independently and in parallel.

References

{{Reflist|refs=

{{cite book |author-first=Behrooz |author-last=Parhami |title=Computer Arithmetic: Algorithms and Hardware Designs |edition=2 |publisher=Oxford University Press |publication-place=New York, USA |date=2010 |isbn=978-0-19-532848-6 |url=http://www.ece.ucsb.edu/~parhami/text_comp_arit.htm |access-date=2021-01-23 |url-status=live |archive-url=https://web.archive.org/web/20200804175912/https://web.ece.ucsb.edu/~parhami/text_comp_arit.htm |archive-date=2020-08-04}} (xxv+641 pages)

{{cite journal |author-last=Isupov |author-first=Konstantin |date=2020-04-07 |orig-date=2020-03-20, 2020-03-08, 2020-02-17 |title=Using Floating-Point Intervals for Non-Modular Computations in Residue Number System |journal=IEEE Access |volume=8 |pages=58603–58619 |doi=10.1109/ACCESS.2020.2982365 |issn=2169-3536 |doi-access=free |bibcode=2020IEEEA...858603I }}

}}

{{cite book |author-last1=Szabo |author-first1=Nicholas S. |author-last2=Tanaka |author-first2=Richard I. |title=Residue Arithmetic and its Applications to Computer Technology |publisher=McGraw-Hill |publication-place=New York, USA |date=1967 |edition=1}}
{{cite book |title=Residue Number System Arithmetic: Modern Applications in Digital Signal Processing |editor-first1=Michael A. |editor-last1=Sonderstrand |editor-first2=W. Kenneth |editor-last2=Jenkins |editor-first3=Graham A. |editor-last3=Jullien |editor-first4=Fred J. |editor-last4=Taylor |series=IEEE Press Reprint Series |publisher=IEEE Circuits and Systems Society, IEEE Press |publication-place=New York, USA |date=1986 |edition=1 |isbn=0-87942-205-X |lccn=86-10516 |id=IEEE order code PC01982}} (viii+418+6 pages)
Chervyakov, N. I.; Molahosseini, A. S.; Lyakhov, P. A. (2017). [https://www.tandfonline.com/doi/abs/10.1080/00207160.2016.1247439 Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem]. International Journal of Computer Mathematics, 94:9, 1833-1849, doi: 10.1080/00207160.2016.1247439.
{{cite journal |author-first=Oleg Anatolevich [Олег Анатольевич] |author-last=Fin'ko [Финько] |url=https://link.springer.com/article/10.1023%2FB%3AAURC.0000030901.74901.44 |title=Large Systems of Boolean Functions: Realization by Modular Arithmetic Methods |journal=Automation and Remote Control |volume=65 |date=June 2004 |number=6 |doi=10.1023/B:AURC.0000030901.74901.44 |s2cid=123623780 |lccn=56038628 |issn=0005-1179 |id={{CODEN|AURCAT}}. {{mathnet|at1588}} |pages=871–892|url-access=subscription }}
Chervyakov, N. I.; Lyakhov, P. A.; Deryabin, M. A. (2020). [https://www.sciencedirect.com/science/article/abs/pii/S092523122030583X Residue Number System-Based Solution for Reducing the Hardware Cost of a Convolutional Neural Network]. Neurocomputing, 407, 439-453, doi: 10.1016/j.neucom.2020.04.018.
{{cite journal |author-first1=Jean-Claude |author-last1=Bajard |author-first2=Nicolas |author-last2=Méloni |author-first3=Thomas |author-last3=Plantard |title=Efficient RNS bases for Cryptography |journal=IMACS'05: World Congress: Scientific Computation Applied Mathematics and Simulation. |date=2006-10-06 |orig-date=July 2005 |location=Paris, France |id=HAL Id: lirmm-00106470 |url=http://hal-lirmm.ccsd.cnrs.fr/docs/00/10/64/70/PDF/D547.PDF |access-date=2021-01-23 |url-status=live |archive-url=https://web.archive.org/web/20210123144923/https://hal-lirmm.ccsd.cnrs.fr/file/index/docid/106470/filename/D547.PDF |archive-date=2021-01-23}} (1+7 pages)
{{cite book |author-first1=Amos |author-last1=Omondi |author-first2=Benjamin |author-last2=Premkumar |title=Residue Number Systems: Theory and Implementation |publisher=Imperial College Press |publication-place=London, UK |date=2007 |isbn=978-1-86094-866-4}} (296 pages)
{{cite book |author-last=Mohan |author-first=P. V. Ananda |title=Residue Number Systems: Theory and Applications |publisher=Birkhäuser / Springer International Publishing Switzerland |doi=10.1007/978-3-319-41385-3 |lccn=2016947081 |date=2016 |edition=1 |isbn=978-3-319-41383-9 |url=https://link.springer.com/book/10.1007%2F978-3-319-41385-3}} (351 pages)
{{cite book |editor-last1=Amir Sabbagh |editor-first1=Molahosseini |editor-first2=Leonel Seabra |editor-last2=de Sousa |editor3=Chip-Hong Chang |title=Embedded Systems Design with Special Arithmetic and Number Systems |publisher=Springer International Publishing AG |date=2017-03-21 |edition=1 |isbn=978-3-319-49741-9 |doi=10.1007/978-3-319-49742-6 |lccn=2017934074 |url=https://link.springer.com/book/10.1007/978-3-319-49742-6}} (389 pages)
{{cite web |title=Division algorithms |url=http://www.cs.rpi.edu/research/ps/93-9.ps |access-date=24 August 2023 |archive-url=https://web.archive.org/web/20050217165652/http://www.cs.rpi.edu/research/ps/93-9.ps |archive-date=17 February 2005}}
{{cite book |author-last=Knuth |author-first=Donald Ervin |author-link=Donald Ervin Knuth |title=The Art of Computer Programming |publisher=Addison Wesley}}
{{cite journal |author-last=Harvey |author-first=David |date=2010 |title=A multimodular algorithm for computing Bernoulli numbers. |journal=Mathematics of Computation |volume=79 |issue=272 |pages=2361–2370|doi=10.1090/S0025-5718-2010-02367-1 |s2cid=11329343 |doi-access=free |arxiv=0807.1347 }}
{{cite journal |author-last1=Lecerf |author-first1=Grégoire |author-last2=Schost |author-first2=Éric |date=2003 |title=Fast multivariate power series multiplication in characteristic zero |journal=SADIO Electronic Journal on Informatics and Operations Research |volume=5 |issue=1 |pages=1–10}}
{{cite journal |author-last1=Orange |author-first1=Sébastien |author-last2=Renault |author-first2=Guénaël |author-last3=Yokoyama |author-first3=Kazuhiro |date=2012 |title=Efficient arithmetic in successive algebraic extension fields using symmetries |journal=Mathematics in Computer Science |volume=6 |issue=3 |pages=217–233|doi=10.1007/s11786-012-0112-y |s2cid=14360845 }}
{{cite book |author-last=Yokoyama |author-first=Kazuhiro |date=September 2012 |chapter=Usage of modular techniques for efficient computation of ideal operations |title=International Workshop on Computer Algebra in Scientific Computing |pages=361–362 |publisher=Springer |publication-place=Berlin / Heidelberg, Germany}}
{{cite book |author-last1=Hladík |author-first1=Jakub |author-last2=Šimeček |author-first2=Ivan |date=January 2012 |chapter=Modular Arithmetic for Solving Linear Equations on the GPU |title=Seminar on Numerical Analysis |pages=68–70}}
{{cite book |author-last=Pernet |author-first=Clément |date=June 2015 |chapter=Exact linear algebra algorithmic: Theory and practice |title=Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation |pages=17–18 |publisher=Association for Computing Machinery}}
{{cite journal |author-last=Lecerf |author-first=Grégoire |date=2018 |title=On the complexity of the Lickteig–Roy subresultant algorithm |journal=Journal of Symbolic Computation}}
{{cite journal |author-last1=Yokoyama |author-first1=Kazuhiro |author-last2=Noro |author-first2=Masayuki |author-last3=Takeshima |author-first3=Taku |date=1994 |title=Multi-Modular Approach to Polynomial-Time Factorization of Bivariate Integral Polynomials |journal=Journal of Symbolic Computation |volume=17 |issue=6 |pages=545–563|doi=10.1006/jsco.1994.1034 |doi-access=free }}
Isupov, Konstantin (2021). "High-Performance Computation in Residue Number System Using Floating-Point Arithmetic". [https://www.mdpi.com/journal/computation Computation]. 9 (2): 9. [http://dx.doi.org/10.3390/computation9020009 doi:10.3390/computation9020009]. ISSN 2079-3197.

Category:Modular arithmetic

Category:Computer arithmetic