1 Introduction
At present, the field of high-performance computing is developing extremely rapidly. That leads to qualitatively new requirements imposed on numerical methods and computing algorithms. Practically, all the well-known approaches to the development of high-performance computing have one trait in common, that essence consists in the application of certain parallel forms of data representation and processing.
One of the most promising avenues to significantly improve the performance and reliability of computing facilities is the implementation of non-conventional methods of number representation, as well as corresponding variants of computer arithmetic. Within the framework of this approach, the non-positional number systems with a parallel structure, in particular, the RNS, occupy a place of special importance [3, 5, 18‐20, 27, 28].
Anzeige
Since its inception in the mid-1950s till the present day, the RNS has attracted the continuous attention of researchers in computer technology, communications, numerical methods, cryptography, and other fields. An RNS, whose ideological roots date back to the standard topics of number theory, has natural internal parallelism. The main advantage of an RNS is a unique ability to decompose the large word-length numbers up into the set of independent short word-length residues, which can be processed in parallel. The carry-free property and speed-up provided by the parallelism of RNS allows carrying out the sequences of modular operations quickly and easily.
Thus, it becomes possible to parallelize the computations at the level of arithmetic operations, which is fundamentally crucial for modern high-performance computing systems. Unlike traditional weighted number systems (WNS), an RNS provides an entirely different approach for increasing the speed and reliability of digital information processing, as well as obtaining new and more advanced computational structures. In this regard, RNS arithmetic is the cornerstone of many modern algorithms of parallel computer algebra, as well as it is in demand in many fundamental applications of science and technology.
Due to the inherent code parallelism, an RNS possesses a few essential advantages over the conventional number system in the field of high-speed computing. A broad class of fast algorithms can be implemented based on modular arithmetic in areas such as digital signal and image processing, distributed information and communication systems, computer networks, information security systems, cloud computing, etc. [19, 20, 27, 30]. Moreover, these RNS algorithms can effectively be applied even to processor platforms functioning according to the conventional information-processing approach based on the weighted binary number system. The parallel and carry-free RNS arithmetic corresponds with high-performance modern embedded systems requirements [19].
However, the numerical solution of a wide range of science and technology problems is often required to perform complicated and heterogeneous processes of computation. In RNS, this results in the need to carry out a set of so-called non-modular operations, such as magnitude comparison, sign determination, overflow detection, general division, scaling, residue-to-binary conversion, etc. The problem of effective implementation of non-modular operations is constantly receiving considerable attention after the formalization of the processing principles in RNS arithmetic [3, 5, 18‐20].
Anzeige
To perform in RNS the non-modular operations, it is not enough to take into account only the individual residues of the modular code. Furthermore, it is necessary to estimate the value of the total number, which, in general, is hampered by the non-positional nature of RNS.
Unfortunately, up until now, the underlying unresolved problem for creating a high-speed RNS arithmetic consists of the computational complexity of non-modular operations. Precisely because of the lack of fast algorithms of non-modular operations, the use of RNS is useful in cases only when the modular addition and multiplication operations make up the bulk of required amounts of computation, and the number of non-modular operations is relatively small. This circumstance restricts the scope of practical applications of RNS to a narrow class of specific tasks, for example, digital filtering, fast Fourier transform, cryptographic transformations, etc.
Therefore, the design of high-performance algorithms for non-modular operations is an urgent problem at the current stage of RNS arithmetic development and its application in computer sciences. To solve this problem is necessary to design efficient approaches and methods for the fast weighted representation of RNS numbers by their residue codes. That will make it possible for the extensive use of RNS arithmetic for high-speed computing in many priority areas of science and technology.
2 The Basic Principles of RNS Arithmetic
The abstract algebra and number theory are formed the theoretical basis of residue arithmetic [6, 11].
In the conventional non-redundant RNS with the set \(\left \{m_{1},m_{2},\dots ,m_{k}\right \}\) of k pairwise relatively prime odd moduli \(\left (m_{i}>2, i=1,2,...,k\right )\), the integer number \(X\in \mathbb {Z}_{M_{k}}\) is represented by an ordered set of residues \(\left (\chi _{1},\chi _{2},\dots ,\chi _{k}\right )\) that is generally called a residue (modular) code, where \(\mathbb {Z}_{M_{k}}=\left \{0,1,\dots ,M_{k}-1\right \}\), \(M_{k}={\prod }_{i=1}^{k}{m_{i}}\), \(\chi _{i}={\left |X\right |}_{m_{i}}\)\(\left (i=1,2,\dots ,k\right )\); \(\left |Y\right |_{m}\) denotes the least non-negative residue of the integer Y modulo m, i.e., \({\left |Y\right |_{m}}\in \mathbb {Z}_{m}=\{0,1,\dots ,m-1\}\).
As is known, the main fundamental advantage of RNS arithmetic as compared with the arithmetic of WNS consists of the performance of addition, subtraction and multiplication operations in parallel at the level of small word-length residues. In other words, these operations decompose into independent components with respect to basic moduli \(m_{1},m_{2},\dots ,m_{k}\). The modular operation \(\circ \in \left \{+,-,\times \right \}\) on the integers \(A=\left (\alpha _{1},\alpha _{2},\dots ,\alpha _{k}\right )\) and \(B=\left (\beta _{1},\beta _{2},\dots ,\beta _{k}\right )\)\((\alpha _{i}={\left |A\right |}_{m_{i}}, \beta _{i}={\left |B\right |}_{m_{i}}, i=1,2,\dots ,k)\) is carried out independently for each of the RNS moduli, i.e., by the rule
$$ \begin{array}{@{}rcl@{}} A\circ B&=&\ \left( \alpha_{1},\alpha_{2},\dots,\alpha_{k}\right) \circ \left( \beta_{1},{\ \beta}_{2},\dots,\beta_{k}\right) \\ &=&\left( {\left|\alpha_{1}\circ\beta_{1}\right|}_{m_{1}}, {\left|\alpha_{2}\circ\beta_{2}\right|} _{m_{2}},\dots,{\left|\alpha_{k}\circ\beta_{k}\right|}_{m_{k}}\right). \end{array} $$
The efficiency of RNS arithmetic is primarily determined by the complexity and performance of non-modular procedures, which are used as essential elementary procedures for implementing more complex computational algorithms. The fundamental principles of designing high-speed variants of RNS arithmetic consist in carrying out the following crucial conditions imposed on non-modular operations: parallelism, high modularity, and simplicity of pipelining at the level of small word-length residue operations.
The root problem in RNS arithmetic is that the integer value of the number \(X=\left (\chi _{1},\chi _{2},\dots ,\chi _{k}\right )\) depends on all its residues together. In the RNS, its evaluation underlies all non-modular operations. As is known, for performing non-modular operations, the so-called positional characteristics of the residue code are used [3, 5, 18‐20]. In general, all these characteristics depend on part or all residues of the number X. They can be defined as a specific mathematical function that, by some method or other, allows estimation of the positional value of X. It is quite clear that the computational complexity of the applied positional characteristics eventually determines the efficiency of RNS arithmetic constructed on their basis.
The traditional implementations of non-modular operations in RNS arithmetic are based on the reverse conversion from residues back to an integer. There are two canonical techniques: the straightforward conversion method based on the CRT algorithm, and the conversion of the residue code to a weighted representation in Mixed-Radix System (MRS) [2, 12, 18‐20, 31]. In general, all other conversion methods are variants of these two main methods.
At the same time, in recent years, the CRT has been intensively studied with its applications in high-performance computing. That led to the development of a sufficiently wide class of specific methods based on the calculation of positional characteristics of RNS numbers, which support effective implementations of non-modular operations. Some of the generally accepted characteristics are the core function, rank function, interval index, parity, diagonal function, and quotient function [1, 3‐5, 7‐10, 15‐17, 19, 21, 22, 24].
Nevertheless, in conventional non-redundant RNS, the calculation of all these characteristics is complicated and quite time-consuming. That is why the non-modular operations limit the applications of RNS arithmetic and restrict its general usage.
3 The Rank of an RNS Number
As is known, in the case of pairwise relatively prime moduli \(m_{1},m_{2},\dots ,m_{k}\) the system of simultaneous linear congruences
has a unique solution that is the residue class modulo Mk specified by the congruence
where Mi,k = Mk/mi, \(\mu _{i,k}={\left |M_{i,k}^{-1}\right |}_{m_{i}}\)\(\left (i=1,2,\dots ,k\right )\); \({\left |Y^{-1}\right |}_{m}\) denotes the multiplicative inverse of the integer Y modulo m.
$$ \begin{array}{@{}rcl@{}} \left\{\begin{array}{c} X \equiv\chi_{1}\pmod{m_{1}},\\ X \equiv\chi_{2}\pmod{m_{2}},\\ {\ldots} \\ X \equiv\chi_{k}\pmod{m_{k}} \end{array}\right. \end{array} $$
$$ X\equiv\left( \sum\limits_{i=1}^{k}{M_{i,k}\mu_{i,k}\chi_{i}}\right)\pmod{M_{k}}, $$
(1)
In the RNS with the set \(m_{1},m_{2},\dots ,m_{k}\) of k pairwise relatively prime moduli it is possible to represent at most Mk integers. Therefore, the set \(\mathbb {Z}_{M_{k}}\) usually used as a dynamic range of the RNS.
Thus, modular coding is defined as a mapping \(\varphi _{RNS}\colon \mathbb {Z}_{M_{k}}\to \mathbb {Z}_{m_{1}}\times \ \mathbb {Z}_{m_{2}}\times \dots \times \ \mathbb {Z}_{m_{k}}\) that assigns the residue code \((\chi _{1},\chi _{2},\dots ,\chi _{k})\) to each \(X\in \mathbb {Z}_{M_{k}}\). At the same time, regarding the decoding mapping \(\varphi _{RNS}^{-1}\colon \mathbb {Z}_{m_{1}}\times \ \mathbb {Z}_{m_{2}} \times \dots \times \ \mathbb {Z}_{m_{k}}\to \mathbb {Z}_{M_{k}}\) based on the relationship (1), the following rule is valid:
where the integer numbers \(B_{1},B_{2},\dots ,B_{k}\) are the basic primitive constants in the given RNS; Bi = Mi,kμi,k, \(i=1,2,\dots ,k\) [3].
$$ X=\left|\sum\limits_{i=1}^{k}{M_{i,k}\mu_{i,k}\chi_{i}}\right|_{M_{k}}=\left|\sum\limits_{i=1}^{k}{B_{i}\chi_{i}}\right|_{M_{k}} \left( X\in \mathbb{Z}_{M_{k}}\right), $$
(2)
As can be seen, the reverse conversion from RNS to WNS by using the straightforward application of (2) requires \(O\left (k\right )\) of large word-lengths addition operations modulo Mk, which is the product of all moduli \(m_{1},m_{2},\dots ,m_{k}\). If we assume that the processing of such long L-bit numbers (\(L=\left \lceil \log _{2}{M_{k}}\right \rceil \)) is comparable in time with k operations on the small residues, then the complexity of this method is equal to \(O\left (k^{2}\right )\) Because of this fact, a given approach is practically unacceptable for high-speed computing, especially in cryptographic applications.
Here and further \(\left \lceil x \right \rceil \) denotes the smallest integer greater than or equal to x.
To circumvent the problem of slow addition operations modulo Mk, the equation (2) can be written as an exact integer equality
where \(r\left (X\right )\) is a non-negative integer called the true rank of the number X [3, 5].
$$ X=\sum\limits_{i=1}^{k}{B_{i}\chi_{i}} - r\left( X\right)M_{k}, $$
(3)
From (3) it follows that the upper bound of \(r\left (X\right )\) depends on weighting factors \(\mu _{1,k},\mu _{2,k},\dots ,\mu _{k,k}\) and it is a rather large value for moduli-sets \(\{m_{1},m_{2},\dots ,m_{k}\}\) suitable for practical application.
By using Euclid’s Division Lemma, we have
where χi,k is a normalized residue modulo mi:
\(\left \lfloor x \right \rfloor \) denotes the largest integer less than or equal to x.
$$ \mu_{i,k}\chi_{i}={\left|\mu_{i,k}\chi_{i}\right|}_{m_{i}}+\left\lfloor\frac{\mu_{i,k}\chi_{i}}{m_{i}}\right\rfloor m_{i}=\chi_{i,k}+\left \lfloor\frac{\mu_{i,k}\chi_{i}}{m_{i}}\right\rfloor m_{i}, $$
(4)
$$ \chi_{i,k}={\left|\mu_{i,k}\chi_{i}\right|}_{m_{i}}={\left|{M}_{i,k}^{-1}\chi_{i}\right|}_{m_{i}} \ \left( i=1,2,\dots,k\right), $$
(5)
Substituting (4) into (2) and taking into consideration (5), we have
that is equivalent to
$$ X=\left|\sum\limits_{i=1}^{k}{M_{i,k}\chi_{i,k}}+M_{k}\sum\limits_{i=1}^{k}{\left\lfloor\frac{\mu_{i,k}\chi_{i}}{m_{i}}\right\rfloor}\right|_{M_{k}} $$
$$ X=\left|\sum\limits_{i=1}^{k}{M_{i,k}\chi_{i,k}}\right|_{M_{k}}=\left|\sum\limits_{i=1}^{k}{M_{i,k}\left|M_{i,k}^{-1}\chi_{i}\right|_{m_{i}}}\right|_{M_{k}}. $$
(6)
Similarly to (3), according to (6), the number X can also be written as
where the integer \(\rho _{k}\left (X\right )\) is the normalized rank (or, briefly, rank) of the number X.
$$ X=\sum\limits_{i=1}^{k}{M_{i,k}\chi_{i,k}}-\rho_{k}\left( X\right)M_{k}, $$
(7)
Equation (7) is called the rank form (or CRT-form) of the number X. In essence, the rank \(\rho _{k}\left (X\right )\) is the CRT reconstruction coefficient that is indicated how many times the RNS dynamic range exceeded when converting the residue code \(\left (\chi _{1},\chi _{2},\dots ,\chi _{k}\right )\) of the number X to its integer value according to (7).
Let us now estimate the upper bound of the rank \(\rho _{k}\left (X\right )\). Dividing (7) by Mk with taking the integer part of both sides of the obtained equality and taking into account the fact that \(\left \lfloor {X}/{M_{k}}\right \rfloor =0\), we have
$$ \rho_{k}\left( X\right)=\left\lfloor\frac{1}{M_{k}}{\sum\limits_{i=1}^{k}{M_{i,k}\chi_{i,k}}}\right\rfloor=\left\lfloor{\sum\limits_{i=1}^{k}{\frac{\chi_{i,k}}{m_{i}}}}\right\rfloor. $$
(8)
Hence, owing to \(\chi _{i,k}\in \mathbb {Z}_{m_{i}}\) \(\left (i=1,2,\dots ,k\right )\) we get the following estimation
$$ \begin{array}{@{}rcl@{}} 0\le\rho_{k}\left( X\right)\le\left\lfloor{\sum\limits_{i=1}^{k}{\frac{m_{i}-1}{m_{i}}}}\right\rfloor &=&k+\left\lfloor-{\sum\limits_{i=1}^{k}{\frac{1}{m_{i}}}}\right\rfloor \\ &=&k-\left\lceil{\sum\limits_{i=1}^{k}{\frac{1}{m_{i}}}}\right\rceil=k-\left\lceil\frac{1}{M_{k}}{\sum\limits_{i=1}^{k}{M_{i,k}}}\right\rceil. \end{array} $$
(9)
Let us consider the number \(Y=\left (\gamma _{1},\gamma _{2},\dots ,\gamma _{k}\right )\), where \(\gamma _{i}=\left |M_{i,k}\right |_{m_{i}}\), \(i=1,2,\dots ,k\). Then, according to (7), we have
because of \(\gamma _{i,k}={\left |M_{i,k}^{-1}\gamma _{i}\right |}_{m_{i}}={\left |M_{i,k}^{-1}M_{i,k}\right |}_{m_{i}}=1\).
$$ Y=\sum\limits_{i=1}^{k}{M_{i,k}\gamma_{i,k}}-\rho_{k}\left( Y\right)M_{k}=\sum\limits_{i=1}^{k}{M_{i,k}}-\rho_{k}\left( Y\right)M_{k} $$
Thus,
$$ \sum\limits_{i=1}^{k}{M_{i,k}}=Y+\rho_{k}\left( Y\right)M_{k}. $$
Therefore, because 0 < Y < Mk, we have
$$ \left\lceil\frac{1}{M_{k}}\sum\limits_{i=1}^{k}{M_{i,k}}\right\rceil=\left\lceil\frac{1}{M_{k}}\left( Y+\rho_{k}\left( Y\right)M_{k}\right)\right\rceil=\rho_{k}\left( Y\right)+\left\lceil\frac{Y}{M_{k}}\right\rceil=\rho_{k}\left( Y\right)+1. $$
Since \(\rho _{k}\left (Y\right )\ge 0\), regardless of the selected moduli-set \(\left \{m_{1},m_{2},\dots ,m_{k}\right \}\), then, according to (9), the following estimation is valid
Hence, \(\rho _{k}\left (X\right )\in \mathbb {Z}_{k}=\left \{0,1,\dots ,k-1\right \}\).
$$ 0\le\rho_{k}\left( X\right)\le k-1-\rho_{k}\left( Y\right)\le k-1. $$
The summands Mi,kχi,k in the equation (6) have smaller values than Mi,kμi,kχi in (2) \(\left (i=1,2,\dots ,k\right )\), so \(\rho _{k}\left (X\right )\) is significantly less than \(r\left (X\right )\). Therefore, the CRT-form (7) in comparison with (3) is a more suitable basis for performing the non-modular operations in RNS arithmetic.
The structure of the rank characteristic and the methods of its calculation in the non-redundant RNS were studied in detail in [3, 5]. At the same time, the main drawback of known approaches is the difficulty in the calculation of the rank and straightforward implementation of the CRT. Consequently, these algorithms are not suitable for designing efficient variants of RNS arithmetic, especially for large word-length numbers.
4 A Novel Method for Calculating the Rank in Non-redundant RNS
In the RNS, the rank \(\rho _{k}\left (X\right )\) is a positional characteristic of the residue code of primary importance since on its basis all non-modular operations can be implemented. Therefore, the development of effective methods and algorithms for calculating the rank \(\rho _{k}\left (X\right )\) occupies an essential place in the practice of applying RNS to construct high-performance modular computational structures.
Knowledge of the rank \(\rho _{k}\left (X\right )\) allows estimation of the integer value of the RNS-number X. It is quite clear that the level of complexity of rank calculation ultimately determines the efficiency of modular arithmetic constructed on its basis.
From the relationship for the CRT-form (7) of the number X it follows that
where
We will call this number the CRT-number of X.
$$ X_{k}=X+\rho_{k}\left( X\right)M_{k}, $$
(10)
$$ X_{k}=\sum\limits_{i=1}^{k}{M_{i,k}\chi_{i,k}}. $$
(11)
Then, by using the following notations: \(M_{k-1}={\prod }_{i=1}^{k-1}{m_{i}}\) and Mi,k− 1 = Mk− 1/mi \(\left (i=1,2,\dots ,k-1\right )\), as well as taking into account that Mi,k = Mk/mi = Mk− 1mk/mi = Mi,k− 1mk and Mk,k = Mk/mk = Mk− 1, we can write the CRT-number Xk (see (11)) as
$$ X_{k}=\sum\limits_{i=1}^{k-1}{M_{i,k}\chi_{i,k}}+M_{k,k}\chi_{k,k}= \sum\limits_{i=1}^{k-1}{M_{i,k-1}m_{k}\chi_{i,k}}+M_{k-1}\chi_{k,k}. $$
(12)
The number mkχi,k in equation (12), according to Euclid’s Division Lemma, can be represented as
taking into account that
$$ m_{k}\chi_{i,k}={\left|m_{k}\chi_{i,k}\right|}_{m_{i}}+\left\lfloor\frac{m_{k}\chi_{i,k}}{m_{i}}\right\rfloor m_{i}=\chi_{i,k-1}+\left\lfloor \frac{m_{k}\chi_{i,k}}{m_{i}}\right\rfloor m_{i}, $$
(13)
$$ {\left|m_{k}\chi_{i,k}\right|}_{m_{i}}= {\left|m_{k}{\left|M_{i,k}^{-1}\chi_{i}\right|}_{m_{i}}\right|}_{m_{i}}={\left|m_{k} M_{i,k}^{-1}\chi_{i}\right|}_{m_{i}}={\left|M_{i,k-1}^{-1}\chi_{i}\right|}_{m_{i}}=\chi_{i,k-1}. $$
Thus,
$$ X_{k}=\sum\limits_{i=1}^{k-1}{M_{i,k-1}\chi_{i,k-1}}+ M_{k-1}\sum\limits_{i=1}^{k-1}{\left\lfloor\frac{m_{k}\chi_{i,k}}{m_{i}}\right\rfloor}+M_{k-1}\chi_{k,k}. $$
Finally, we have
where
$$ X_{k}=X_{k-1}+M_{k-1}S_{k}\left( X\right), $$
(14)
$$ X_{k-1}=\sum\limits_{i=1}^{k-1}{M_{i,k-1}\chi_{i,k-1}}, $$
(15)
$$ S_{k}\left( X\right)=\sum\limits_{i=1}^{k}{R_{i,k}\left( \chi_{i}\right)}, $$
(16)
$$ R_{i,k}\left( \chi_{i}\right)=\left\lfloor\frac{m_{k}\chi_{i,k}}{m_{i}}\right\rfloor \ \left( i=1,2,\dots,k\right). $$
(17)
Remark 1
Taking into account (13), we have
As far as \(R_{i,k}\left (\chi _{i}\right )\in \mathbb {Z}_{m_{k}}\), we can then obtain a residue modulo mk on both sides of this equality. Hence, it then follows that
for \(i=1,2,\dots ,k-1\). At the same time, according to (17),
$$ R_{i,k}\left( \chi_{i}\right)=\frac{m_{k}\chi_{i,k}-\chi_{i,k-1}}{m_{i}}. $$
$$ R_{i,k}\left( \chi_{i}\right)={\left|\frac{m_{k}\chi_{i,k}-\chi_{i,k-1}}{m_{i}}\right|}_{m_{k}}={\left|-\frac{\chi_{i,k-1}}{m_{i}}\right|}_{m_{k}}={\left|-\frac{{\left|M_{i,k-1}^{-1}\chi_{i}\right|}_{m_{i}}}{m_{i}}\right|}_{m_{k}} $$
(18)
$$ R_{k,k}\left( \chi_{k}\right)=\chi_{k,k}={\left|M_{k,k}^{-1}\chi_{k}\right|}_{m_{k}}={\left|M_{k-1}^{-1}\chi_{k}\right|}_{m_{k}}. $$
(19)
Similarly, as described above for the number Xk (see (14)–(16)), the numbers Xi \(\left (i=k-1,k-2,\dots ,1\right )\) can be written as
where M0 = 1, \(S_{1}\left (X\right )=\chi _{1}\).
$$ \begin{array}{@{}rcl@{}} X_{k-1}&=&X_{k-2}+M_{k-2}S_{k-1}\left( X\right), \\ X_{k-2}&=&X_{k-3}+M_{k-3}S_{k-2}\left( X\right), \\ &\ldots \\ X_{2}&=&X_{1}+M_{1} S_{2}\left( X\right), \\ X_{1}&=&M_{0} S_{1}\left( X\right), \end{array} $$
Finally, the CRT-number Xk can be represented as
where \(M_{l-1}={\prod }_{i=1}^{l-1}{m_{i}}\).
$$ X_{k}=\sum\limits_{l=1}^{k}{M_{l-1}S_{l}\left( X\right)}, $$
(20)
The integer \(S_{l}\left (X\right )\) for \(l=2,3,\dots , k\) using Euclid’s Division Lemma can be written as
At the same time,
where
Mi,l− 1 = Ml− 1/mi.
$$ S_{l}\left( X\right)=R_{l}\left( X\right)+m_{l} Q_{l}\left( X\right). $$
(21)
$$ R_{l}\left( X\right)={\left|S_{l}\left( X\right)\right|}_{m_{l}}=\left|\sum\limits_{i=1}^{l}{R_{i,l}(\chi_{i})}\right|_{m_{l}}, $$
(22)
$$ Q_{l}\left( X\right)=\left\lfloor\frac{1}{m_{l}}S_{l}\left( X\right)\right\rfloor=\left\lfloor\frac{1}{m_{l}}\sum\limits_{i=1}^{l}{R_{i,l}(\chi_{i})}\right\rfloor, $$
(23)
$$ R_{i,l}\left( \chi_{i}\right)={\left|-\frac{\left|M_{i,l-1}^{-1}\chi_{i}\right|_{m_{i}}}{m_{i}}\right|}_{m_{l}} \left( i\neq l\right), $$
(24)
$$ R_{l,l}\left( \chi_{l}\right)=\chi_{l,l}={\left|M_{l-1}^{-1}\chi_{l}\right|}_{m_{l}}, $$
(25)
It is evident that \(Q_{l}\left (X\right )\) is equal to the number of overflows that occurred when calculating the sum \(R_{l}\left (X\right )\) of l residues \(R_{1,l}\left (\chi _{1}\right ),R_{2,l}\left (\chi _{2}\right ),\dots ,R_{l,l}\left (\chi _{l}\right )\) modulo \(m_{l}\ \left (l=2,3,\dots ,k\right )\).
It can be noted that \(R_{1}\left (X\right )=\chi _{1}\) and \(Q_{1}\left (X\right )=0\) since \(S_{1}\left (X\right )=\chi _{1}\).
Taking into account (20) and (21), we have
$$ \begin{array}{@{}rcl@{}} X_{k}&=&\sum\limits_{l=1}^{k}{M_{l-1}\left( R_{l}\left( X\right)+m_{l} Q_{l}\left( X\right)\right)}\\ &=&\sum\limits_{l=1}^{k}{M_{l-1}R_{l}\left( X\right)}+\sum\limits_{l=1}^{k}{M_{l}Q_{l}\left( X\right)}\\ &=&\sum\limits_{l=1}^{k}{M_{l-1}R_{l}\left( X\right)}+\sum\limits_{l=1}^{k-1}{M_{l}Q_{l}\left( X\right)}+M_{k}Q_{k}\left( X\right). \end{array} $$
Thus,
where
$$ X_{k}={X}_{k}^{\left( R\right)}+X^{\left( Q\right)}_{k-1}+M_{k}Q_{k}\left( X\right), $$
(26)
$$ {X}_{k}^{\left( R\right)}=\sum\limits_{l=1}^{k}{M_{l-1}R_{l}\left( X\right)}, $$
(27)
$$ {X}_{k-1}^{\left( Q\right)}=\sum\limits_{l=1}^{k-1}{M_{l}Q_{l}\left( X\right)}. $$
(28)
As is known, in the MRS based on the moduli-set \(\{m_{1},m_{2},\dots ,m_{k}\}\) the integer \(X\in \mathbb {Z}_{M_{k}}\) is represented by the k-tuple \(\langle x_{k},x_{k-1},\dots ,x_{1}\rangle \) of mixed-radix digits, resulting in
where \(x_{i}\in \mathbb {Z}_{m_{i}}=\{0,1,\dots ,m_{i}-1\}, i=1,2,\dots ,k\) [18‐20].
$$ X=x_{1}+x_{2}M_{1}+\dots+x_{k} M_{k-1}= \sum\limits_{i=1}^{k}{x_{i}M_{i-1}}, $$
As follows from equation (27), the number \({X}_{k}^{\left (R\right )}\) is represented by the k-tuple \({\left \langle {x}_{k}^{\left (R\right )},{x}_{k-1}^{\left (R\right )},\dots ,{x}_{1}^{\left (R\right )}\right \rangle }\) of mixed-radix digits \(x_{l}^{\left (R\right )}=R_{l}\left (X\right )\), \(R_{l}\left (X\right )\in \mathbb {Z}_{m_{l}}\), \(l=1,2,\dots ,k\). It is evident that \(X_{k}^{\left (R\right )}<M_{k}\).
As for the number \({X}_{k-1}^{\left (Q\right )}\) (see (28)), it can be written as
where \({\widehat {Q}}_{1}\left (X\right )=0\), \({\widehat {Q}}_{2}\left (X\right )=Q_{1}\left (X\right )=0\), \({\widehat {Q}}_{l}\left (X\right )=Q_{l-1}\left (X\right )\) \(\left (l=3,4,\dots ,k\right )\).
$$ {X}_{k-1}^{\left( Q\right)}=\sum\limits_{l=2}^{k}{M_{l-1}Q_{l-1}\left( X\right)}=\sum\limits_{l=1}^{k}{M_{l-1}{\widehat{Q}}_{l}\left( X\right)}, $$
At the same time, as follows from (23) in the case when the subscript l is substituted by l − 1,
because of the residue Ri,l− 1(χi) ≤ ml− 1 − 1 \(\left (l=3,4,\dots ,k\right )\).
$$ {\widehat{Q}}_{l}\left( X\right)=Q_{l-1}\left( X\right)=\left\lfloor\frac{1}{m_{l-1}}\sum\limits_{i=1}^{l-1}{R_{i,l-1}(\chi_{i})}\right\rfloor < l-1 $$
Thus, \({\widehat {Q}}_{l}\left (X\right )\in \mathbb {Z}_{l-1}=\left \{0,1,\dots ,l-2\right \}\). Hence, \({X}_{k-1}^{\left (Q\right )}\) can be considered as a mixed-radix number \(\left \langle x_{k}^{\left (Q\right )},x_{k-1}^{\left (Q\right )},\dots ,x_{1}^{\left (Q\right )}\right \rangle \)\(\left ({x}_{1}^{\left (Q\right )}={x}_{2}^{\left (Q\right )}=0; {x}_{l}^{\left (Q\right )}=Q_{l-1}\right .\) \(\left .\left (X\right ), l=3,4,\dots ,k\vphantom {{x}_{1}^{\left (Q\right )}}\right )\) in the case if \(x_{l}^{\left (Q\right )}\in \mathbb {Z}_{m_{l}}\). Therefore, the following condition must be met: \(\mathbb {Z}_{l-1}\subseteq \mathbb {Z}_{m_{l}}\) for all l. This leads to inequality
$$ m_{l} \ge l-1 \ \left( l=1,2,\dots,k\right). $$
If the moduli-set \(\left \{m_{1},m_{2},\dots ,m_{k}\right \}\) is chosen according to this condition, which as a rule always holds for the RNS used in practical applications, then \({X}_{k-1}^{\left (Q\right )}\in \mathbb {Z}_{M_{k}}\), that is \({X}_{k-1}^{\left (Q\right )}<M_{k}\).
Thus,
According to Euclid’s Division Lemma,
$$ 0 \le {X}_{k}^{\left( R\right)}+{X}_{k-1}^{\left( Q\right)} \le 2\left( M_{k}-1\right). $$
(29)
$$ {X}_{k}^{\left( R\right)}+{X}_{k-1}^{\left( Q\right)}={\left|{X}_{k}^{\left( R\right)}+{X}_{k-1}^{\left( Q\right)}\right|}_{M_{k}}+M_{k}\left\lfloor\frac{{X}_{k}^{\left( R\right)}+{X}_{k-1}^{\left( Q\right)}}{M_{k}}\right\rfloor. $$
Therefore, from (26) we have
$$ X_{k}={\left|{X}_{k}^{\left( R\right)}+{X}_{k-1}^{\left( Q\right)}\right|}_{M_{k}}+M_{k}\left( Q_{k}\left( X\right)+\left\lfloor\frac{{X}_{k}^{\left( R\right)}+{X}_{k-1}^{\left( Q\right)}}{M_{k}}\right\rfloor\right). $$
(30)
From equation (30), according to (10), it follows that
where
$$ X={\left|{X}_{k}^{\left( R\right)}+{X}_{k-1}^{\left( Q\right)}\right|}_{M_{k}}, $$
(31)
$$ \rho_{k}\left( X\right)={\widehat\rho}_{k}\left( X\right)+{\varDelta}_{k}\left( X\right), $$
(32)
$$ {\widehat\rho}_{k}\left( X\right)=Q_{k}\left( X\right), $$
(33)
$$ {\varDelta}_{k}\left( X\right)=\left\lfloor\frac{{X}_{k}^{\left( R\right)}+{X}_{k-1}^{\left( Q\right)}}{M_{k}}\right\rfloor. $$
(34)
Taking into account (29), we have that \({\varDelta }_{k}\left (X\right )\le 1\), that is \({\varDelta }_{k}\left (X\right )\in \mathbb {Z}_{2}=\left \{0,1\right \}\).
We will call the integers \({\widehat \rho }_{k}\left (X\right )\) and \({\varDelta }_{k}\left (X\right )\) the inexact rank and the rank correction, respectively.
The reasons stated above allow us to formulate the following theorem.
Theorem 1 (About the rank of an RNS number)
Let an arbitrary RNS be defined as an ordered set of k pairwise relatively prime odd moduli \(m_{1},m_{2},\dots ,m_{k}\) (ml ≥ l − 1, \(l=1,2,\dots ,k\), k ≥ 2). Then the rank \(\rho _{k}\left (X\right )\) of the integer \(X=\left (\chi _{1},\chi _{2},\dots ,\chi _{k}\right )\) \(\left (X\in \mathbb {Z}_{M_{k}}\right )\) can be computed as follows:
where
and
the correction \({\varDelta }_{k}\left (X\right )\) is a two-valued number that only takes on the values 0 or 1.
$$ \rho_{k}\left( X\right)={\widehat\rho}_{k}\left( X\right)+{\varDelta}_{k}\left( X\right), $$
$$ {\widehat\rho}_{k}\left( X\right)=\left\lfloor\frac{1}{m_{k}}\sum\limits_{i=1}^{k}{R_{i,k}(\chi_{i})}\right\rfloor $$
$$ R_{i,k}(\chi_{i})=\left\lfloor\frac{m_{k}{\left|{M}_{i,k}^{-1}\chi_{i}\right|}_{m_{i}}}{m_{i}}\right\rfloor={\left|-\frac{{\left|{M}_{i,k-1}^{-1}\chi_{i}\right|}_{m_{i}}}{m_{i}}\right|}_{m_{k}}\ \left( i \neq k\right), $$
$$ R_{k,k}(\chi_{k})=\chi_{k,k}={\left|{M}_{k-1}^{-1}\chi_{k}\right|}_{m_{k}}, $$
As it follows from Theorem 1, the inexact rank \({\widehat \rho }_{k}\left (X\right )\in \mathbb {Z}_{k}\) is equal to the number of overflows, which occur when computing the sum of k residues R1,k(χ1), R2,k(χ2), \(\dots \), Rk,k(χk) with respect to the k th modulus mk. Thus, the inexact rank \({\widehat \rho }_{k}\left (X\right )\) can be computed quickly and easily.
A different situation takes place in the case of the rank correction \({\varDelta }_{k}\left (X\right )\) as far as the calculation of its value has a more massive computational complexity than the estimation of the inexact rank \({\widehat \rho }_{k}\left (X\right )\).
As follows from the equations (29) and (34), the rank correction \({\varDelta }_{k}\left (X\right )\) is, in essence, an overflow flag
$$ \begin{array}{@{}rcl@{}} {\varDelta}_{k}\left( X\right)=\left\{\begin{array}{c} 0, \text{if}\ X_{k}^{\left( R\right)}+X_{k-1}^{\left( Q\right)}<M_{k} \\ \\ 1, \text{if}\ X_{k}^{\left( R\right)}+X_{k-1}^{\left( Q\right)} \ge M_{k}. \end{array} \right. \end{array} $$
(35)
To get \({\varDelta }_{k}\left (X\right )\), one must first calculate the k-tuple mixed-radix representations \(\left \langle {x}_{k}^{\left (R\right )},{x}_{k-1}^{\left (R\right )},\dots ,{x}_{1}^{\left (R\right )}\right \rangle \) and \(\left \langle {x}_{k}^{\left (Q\right )},{x}_{k-1}^{\left (Q\right )},\dots ,{x}_{1}^{\left (Q\right )}\right \rangle \) of the integers \({X}_{k}^{\left (R\right )}\) and \({X}_{k-1}^{\left (Q\right )}\), respectively. The digits \({x}_{l}^{\left (R\right )}\) and \({x}_{l}^{\left (Q\right )}\)\(\left (l=2,3,\dots ,k\right )\) are calculated by taking the sum of l residues \(R_{1,l}(\chi _{1}),R_{2,l}(\chi _{2}),\dots ,R_{l,l}(\chi _{l})\) modulo ml according to (22)–(25), followed by the necessity to determine whether the sum of two MRS-numbers \(X_{k}^{\left (R\right )}\) and \({X}_{k-1}^{\left (Q\right )}\) overruns the RNS dynamic range \(\mathbb {Z}_{M_{k}}\).
To illustrate the calculation of the rank in conventional non-redundant RNS based on the mentioned above, we present a first numerical example.
Example 1
Let us consider an RNS with the moduli m1 = 5,m2 = 7,m3 = 9 and m4 = 11. Suppose we wish to calculate the rank \(\rho _{k}\left (X\right )\) of the number X = 2 having the residue code \(\left (\chi _{1},\chi _{2},\chi _{3},\chi _{4}\right )=\left (2,2,2,2\right )\).
The primitive constants in the given RNS are
$$ \begin{array}{@{}rcl@{}} &&M_{4}=3465,\ M_{3}=315,\ M_{2}=35,\ M_{1}=5,\ M_{0}=1.\\ && M_{1,4}=693,\ M_{2,4}=495,\ M_{3,4}=385,\ M_{4,4}=M_{3}=315,\\ && \left|{M}_{1,4}^{-1}\right|_{5}=\left|693^{-1}\right|_{5}=2,\ \left|{M}_{2,4}^{-1}\right|_{7}=\left|495^{-1}\right|_{7}=3,\\ && \left|{M}_{3,4}^{-1}\right|_{9}=\left|385^{-1}\right|_{9}=4,\ \left|{M}_{4,4}^{-1}\right|_{11}=\left|315^{-1}\right|_{11}=8,\\ && \left|5^{-1}\right|_{11}=9, \ \left|7^{-1}\right|_{11}=8,\ \left|9^{-1}\right|_{11}=5, \left|{M}_{3}^{-1}\right|_{11}=\left|315^{-1}\right|_{11}=8.\\ && M_{1,3}=63,\ M_{2,3}=45,\ M_{3,3}=M_{2}=35,\\ && \left|{M}_{1,3}^{-1}\right|_{5}=\left|63^{-1}\right|_{5}=2,\ \left|M_{2,3}^{-1}\right|_{7}=\left|45^{-1}\right|_{7}=5, \ \left|M_{3,3}^{-1}\right|_{9}=\left|35^{-1}\right|_{9}=8,\\ &&\left|5^{-1}\right|_{9}=2,\ \left|7^{-1}\right|_{9}=4;\ \left|M_{2}^{-1}\right|_{9}=\left|35^{-1}\right|_{9}=8.\\ && M_{1,2}=7,\ M_{2,2}=M_{1}=5,\\ && \left|M_{1,2}^{-1}\right|_{5}=\left|7^{-1}\right|_{5}=3,\ \left|M_{2,2}^{-1}\right|_{7}=\left|5^{-1}\right|_{7}=3.\\ && M_{1,1}=1. \end{array} $$
First, according to (24) and (25), we calculate the residue R1,1(χ1) and the sets of residues \(\langle R_{1,l}(\chi _{1}),R_{2,l}(\chi _{2}),\dots ,R_{l,l}(\chi _{l})\rangle \) \(\left (l=2,3,4\right )\):
$$ \begin{array}{@{}rcl@{}} && R_{1,1}\left( \chi_{1}\right)=2;\\ && R_{1,2}\left( \chi_{1}\right)=\left|-\left|1\cdot 2\right|_{7}\cdot 3\right|_{7}=1,\\ && R_{2,2}\left( \chi_{2}\right)=\left|3\cdot 2\right|_{7}=6.\\ && R_{1,3}\left( \chi_{1}\right)=\left|-\left|3\cdot 2\right|_{5}\cdot 2\right|_{9}=7,\\ && R_{2,3}\left( \chi_{2}\right)=\left|-\left|3\cdot 2\right|_{7}\cdot 4\right|_{9}=3,\\ && R_{3,3}\left( \chi_{3}\right)=\left|8\cdot 2\right|_{9}=7.\\ && R_{1,4}\left( \chi_{1}\right)=\left|-\left|2\cdot 2\right|_{5}\cdot 9\right|_{11}=8,\\ && R_{2,4}\left( \chi_{2}\right)=\left|-\left|5\cdot 2\right|_{7}\cdot 8\right|_{11}=9,\\ && R_{3,4}\left( \chi_{3}\right)=\left|-\left|8\cdot 2\right|_{9}\cdot 5\right|_{11}=9,\\ && R_{4,4}\left( \chi_{4}\right)=\left|8\cdot 2\right|_{11}=5. \end{array} $$
Thus, as a result, we have
$$ \begin{array}{@{}rcl@{}} &&\langle R_{1,1}\left( \chi_{1}\right)\rangle=\langle 2\rangle,\\ &&\langle R_{1,2}\left( \chi_{1}\right),R_{2,2}\left( \chi_{2}\right)\rangle=\langle 1, 6\rangle,\\ &&\langle R_{1,3}\left( \chi_{1}\right),R_{2,3}\left( \chi_{2}\right),R_{3,3}\left( \chi_{3}\right)\rangle=\langle 7, 3, 7\rangle,\\ &&\langle R_{1,4}\left( \chi_{1}\right),R_{2,4}\left( \chi_{2}\right),R_{3,4}\left( \chi_{3}\right),R_{4,4}\left( \chi_{4}\right)\rangle=\langle 8, 9, 9, 5\rangle. \end{array} $$
Further, we compute the sum of the corresponding set of residues modulo ml and the number of occurred overflows according to (22) and (23) for l = 2,3,4. Taking into account that \(R_{1}\left (X\right )=R_{1,1}(\chi _{1})\) and \(Q_{1}\left (X\right )=0\), we have
$$ \begin{array}{@{}rcl@{}} &&R_{1}\left( X\right)=2,\\ &&R_{2}\left( X\right)=\left|1+6\right|_{7}=\left|7\right|_{7}=0,\\ &&R_{3}\left( X\right)=\left|7+3+7\right|_{9}=\left|17\right|_{9}=8,\\ &&R_{4}\left( X\right)=\left|8+9+9+5\right|_{11}=\left|31\right|_{11}=9\\ \end{array} $$
and
$$ \begin{array}{@{}rcl@{}} &&Q_{1}\left( X\right)=0,\\ &&Q_{2}\left( X\right)=\left\lfloor{\left( 1+6\right)}/{7}\right\rfloor=\left\lfloor{7}/{7}\right\rfloor=1;\\ &&Q_{3}\left( X\right)=\left\lfloor{\left( 7+3+7\right)}/{9}\right\rfloor=\left\lfloor{17}/{9}\right\rfloor=1;\\ &&Q_{4}\left( X\right)=\left\lfloor{\left( 8+9+9+5\right)}/{11}\right\rfloor=\left\lfloor{31}/{11}\right\rfloor=2. \end{array} $$
Therefore, according to the equations (26)–(28), we obtain the inexact rank
as well as the MRS-integers
and
$$ {\widehat\rho}_{4}\left( X\right)=Q_{4}\left( X\right)=2 $$
$$ {X}_{4}^{\left( R\right)}={\langle 9,8,0,2 \rangle} $$
$$ {X}_{3}^{\left( Q\right)}={\langle 1,1,0,0 \rangle}. $$
Then, by taking the sum of the numbers \({X}_{4}^{\left (R\right )}\) and \({X}_{3}^{\left (Q\right )}\) in the MRS, we get the positional mixed-radix representation of the number X:
as well as the correction \({\varDelta }_{4}\left (X\right )=1\) (see (35)).
$$ X=\left|X_{4}\right|_{M_{4}}=\left|{X}_{4}^{\left( R\right)}+{X}_{3}^{\left( Q\right)}\right|_{M_{4}}=\langle 0,0,0,2 \rangle $$
Finally, we have
$$ \rho_{4}\left( X\right)={\widehat\rho}_{4}\left( X\right)+{\varDelta}_{4}\left( X\right)=2+1=3. $$
To verify the obtained result, taking into account that the normalized residues \(\chi _{l,4} \ \left (l=1,2,3,4\right )\) (see (5)) in the CRT-form (7) take on the following values
$$ \begin{array}{@{}rcl@{}} &\chi_{1,4}={\left|{M}_{1,4}^{-1}\chi_{1}\right|}_{5}={\left|2\cdot2\right|}_{5}=4,\\ &\chi_{2,4}={\left|{M}_{2,4}^{-1}\chi_{2}\right|}_{7}={\left|3\cdot2\right|}_{7}=6,\\ &\chi_{3,4}={\left|{M}_{3,4}^{-1}\chi_{3}\right|}_{9}={\left|4\cdot2\right|}_{9}=8;\\ &\chi_{4,4}={\left|{M}_{3}^{-1}\chi_{4}\right|}_{11}={\left|8\cdot2\right|}_{11}=5\\ \end{array} $$
we find
$$ \begin{array}{@{}rcl@{}} X&=&\ \sum\limits_{i=1}^{4}{M_{i,4}\chi_{i,4}}-\rho_{4}\left( X\right)M_{4}\\ &=&\ 693\cdot 4+ 495\cdot 6+ 385\cdot 8+ 315\cdot 5-3\cdot 3465 \\ &=&\ 10397-10395=2. \end{array} $$
Equations (21)–(28) show that the calculation of the rank \(\rho _{k}\left (X\right )\) in the conventional non-redundant RNS is reduced to a summation of the sets of small residues with respect to the moduli \(m_{1},m_{2},\dots ,m_{k}\). These calculations can be implemented within the framework of tabular computing structures. Also, along with the calculation of the rank \(\rho _{k}\left (X\right )\), we obtain the positional representation of the number X in the MRS. Thus, the computational complexity of calculating the correction \({\varDelta }_{k}\left (X\right )\) (and, hence, the rank \(\rho _{k}\left (X\right )\)) coincides with the computational complexity of converting the residue code into the MRS representation.
From the above, it follows that the main computational cost is the calculation of the rank correction \({\varDelta }_{k}\left (X\right )\). As follows from the equations (21)–(34), during the calculation of \({\varDelta }_{k}\left (X\right )\) we can perform the independent and concurrent summations of the sets of residues \(\langle R_{1,l}(\chi _{1}),R_{2,l}(\chi _{2}),\dots ,R_{l,l}(\chi _{l})\rangle \) with respect to the corresponding modulus ml \(\left (l=2,3,\dots ,k\right )\).
Now let us evaluate the computational costs of the rank calculation. The number of required single one-input lookup tables to store the set of residues \(R_{1,l}(\chi _{1}),R_{2,l}(\chi _{2}),\dots ,R_{l,l}(\chi _{l})\) (see (24) and (25)) is equal to \(n_{LUT}\left (l\right )=l\), while the bit length of recorded constants is \(\left \lceil \log _{2}{m_{l}}\right \rceil \ \left (l=2,3,\dots ,k\right )\). It should be noted that \(n_{LUT}\left (1\right )=0\) since in the case of the modulus m1 we have \(S_{1}\left (X\right )=\chi _{1}\). Then, the total number of required lookup tables
$$ N_{LUT}=\sum\limits_{l=2}^{k}{n_{LUT}\left( l\right)}=\frac{k^{2}+k-2}{2}. $$
(36)
The summation of the set of residues \(\langle R_{1,l}(\chi _{1}),R_{2,l}(\chi _{2}),\dots ,R_{l,l}(\chi _{l})\rangle \) modulo ml along with the counting of the number of occurred overflows requires \(n_{MO}\left (l\right )=l-1\) modular operations \(\left (l=2,3,\dots ,k\right )\). Taking into account that \(x_{1}^{\left (Q\right )}=x_{2}^{\left (Q\right )}=0\), the summation of MRS-numbers \(X_{k}^{\left (R\right )}\) and \(X_{k-1}^{\left (Q\right )}\) along with the detection of overflow flag \({\varDelta }_{k}\left (X\right )\) (see (35)) and the final correction of inexact rank \({\widehat \rho }_{k}\left (X\right )\) requires \(2\left (k-2\right )\) modular addition operations. Hence, the total number of required modular operations
$$ N_{MO}=\sum\limits_{l=2}^{k}{n_{MO}\left( l\right)}+2\left( k-2\right)=\frac{k^{2}+5k-10}{2}. $$
(37)
Therefore, the process of calculating the rank \(\rho _{k}\left (X\right )\) requires O(k2) modular operations so that it can become computationally expensive for large values of k. Thus, for effective implementation of non-modular operations based on the CRT, one needs to speed up and optimize the calculation of the rank correction \({\varDelta }_{k}\left (X\right )\).
5 The Relationship Between the Rank Correction and the Parity of an RNS Number
The fact that \({\varDelta }_{k}\left (X\right )\in \{0,1\}\) (see Theorem 1) allows us to consider it as the residue modulo 2.
According to the CRT-form (7), taking into account (32), we have
where
$$ X=\sum\limits_{i=1}^{k}{M_{i,k}\chi_{i,k}}-\left( {\widehat\rho}_{k}\left( X\right)+{\varDelta}_{k}\left( X\right)\right)M_{k}=\widehat{X}-{\varDelta}_{k}\left( X\right)M_{k}, $$
(38)
$$ \widehat{X}=\sum\limits_{i=1}^{k}{M_{i,k}\chi_{i,k}}-{\widehat\rho}_{k}\left( X\right)M_{k}. $$
(39)
Since the RNS moduli \(m_{1},m_{2},\dots ,m_{k}\) are relatively prime odd integers, then \(|m_{i}|_{2}=1\ \left (i=1,2,\dots ,k\right )\), and correspondingly, |Mk|2 = 1. Therefore,
$$ \left|X\right|_{2}=\left|\widehat{X}-{\varDelta}_{k}\left( X\right)M_{k}\right|_{2}=\left|\left|\widehat{X}\right|_{2}-{\varDelta}_{k}\left( X\right)\right|_{2}. $$
(40)
Thus, for the rank correction \({\varDelta }_{k}\left (X\right )\) the following equality is true
$$ {\varDelta}_{k}\left( X\right)=\left|\left|\widehat{X}\right|_{2}-\left|X\right|_{2}\right|_{2}. $$
(41)
Hence, the calculation of the rank correction \({\varDelta }_{k}\left (X\right )\in \{0,1\}\) can be reduced to a parity comparison of the numbers X and \(\widehat {X}\), that is:
$$ \begin{array}{@{}rcl@{}} {\varDelta}_{k}\left( X\right)=\left\{ \begin{array}{l} 0,\ \text{if}\ \left|X\right|_{2}=|\widehat{X}|_{2}, \\ \\ 1,\ \text{if}\ \left|X\right|_{2}\neq|\widehat{X}|_{2}. \end{array}\right. \end{array} $$
(42)
Taking into account the fact that |Mi,k|2 = 1 \(\left (i=1,2,\dots ,k\right )\), the calculation of the parity of a number \(\widehat {X}\) according to (39) is reduced to performing trivial operations modulo 2, such as
where
and
are the least-significant bits of the binary representation of the normalized residue χi,k \(\left (i=1,2,\dots ,k\right )\) and the inexact rank \({\widehat \rho }_{k}\left (X\right )\), respectively.
$$ \left|\widehat{X}\right|_{2}=\left|\sum\limits_{i=1}^{k}{\left|\chi_{i,k}\right|_{2}}-\left|{\widehat\rho}_{k}\left( X\right)\right|_{2}\right|_{2}=\left|\sum\limits_{i=1}^{k}{{\chi}_{i,k}^{\left( 0\right)}}-{\widehat\rho}_{k}^{\left( 0\right)}\right|_{2}, $$
(43)
$$ {\chi}_{i,k}^{\left( 0\right)}=\left|\chi_{i,k}\right|_{2}=\left|\left|{M}_{i,k-1}^{-1}\chi_{i}\right|_{m_{i}}\right|_{2} $$
(44)
$$ {\widehat\rho}_{k}^{\left( 0\right)}=\left|{\widehat\rho}_{k}\left( X\right)\right|_{2} $$
(45)
As follows from Theorem 1, the inexact rank \({\widehat \rho }_{k}\left (X\right )\), and hence, its parity \({\widehat \rho }_{k}^{\left (0\right )}\) is calculated quickly during the summation of corresponding residues modulo mk. Thus, the calculation of the parity of the number \(\widehat {X}\) according to (43) does not cause difficulties.
Regarding the parity check of the number X, this operation in RNS arithmetic refers to complicated non-modular operations requiring high computational costs. In conventional non-redundant RNS, the computational complexity of this operation is comparable to the computational complexity of RNS to MRS conversion.
Therefore, for fast calculation of the correction \({\varDelta }_{k}\left (X\right )\) according to (42), the complexity of computing parity \(\left |X\right |_{2}\) can be overcome by adding the redundant residue modulo 2 into conventional non-redundant residue code \(\left (\chi _{1},\chi _{2},\dots ,\chi _{k}\right )\) of the number X. Thus, the case in question is the use of redundant RNS, in which only one extra bit is added to the primary residue code.
6 Fast Calculation of the Rank in Minimally Redundant RNS
As is known, the use of code redundancy often allows improving the arithmetic and other properties of numerical systems, including an RNS. In the first place, the redundant RNS are of interest concerning error checking and failure recovery properties [18‐20]. On the other hand, the use of RNS representations with redundant residues is an established method that allows gaining speed and cost benefits when performing various non-modular operations [13, 23, 25, 29].
The proposed redundant residue coding assumes the extension of the modular code \(\left (\chi _{1},\chi _{2},\dots ,\chi _{k}\right )\) of the number X in the conventional non-redundant RNS with the k-moduli set \(\left \{m_{1},m_{2},\dots ,m_{k}\right \}\) and the dynamic range \(\mathbb {Z}_{M_{k}}\) by the redundant residue \({\chi _{0}=\left |X\right |}_{m_{0}}\) with respect to the extra modulus m0 = 2, i.e., by adding the parity of the number X to its residue representation. Thus, in the redundant RNS the number \(X\in \mathbb {Z}_{M_{k}}\) is represented by its redundant residue code \(\left (\chi _{0},\chi _{1},\dots ,\chi _{k}\right )\).
This modular code is, of course, minimally redundant since the total code length increases by only one bit. The redundancy is estimated by the following index
$$ R_{RRNS}=1-\frac{\log_{2}{M_{k}}}{\log_{2}{\left( m_{0}M_{k}\right)}}= \frac{1}{1+\log_{2}{M_{k}}}. $$
(46)
From (46), it follows that the code redundancy decreases as the number k of RNS moduli, and, consequently, the dynamic range \(\mathbb {Z}_{M_{k}}\) increases.
In this case, the main advantage of minimally redundant RNS in comparison with non-redundant RNS consists of a significantly simplified calculation of the rank correction \({\varDelta }_{k}\left (X\right )\) and, accordingly, the rank \(\rho _{k}\left (X\right )\). That leads in turn to optimization and speed-up of non-modular operations in terms of the CRT. The following statement reveals the essence of such an approach.
Theorem 2 (About the rank of a number in minimally redundant RNS)
Let a minimally redundant RNS be defined by an ordered set of k pairwise relatively prime odd moduli m1, m2, \(\dots \), mk and excess modulus m0, \((m_{0}=2;\ m_{l} \ge l-1, l=1,2,\dots ,k;\ k \ge 2)\). Then the rank \(\rho _{k}\left (X\right )\) of the integer \(X=\left (\chi _{0},\chi _{1},\dots ,\chi _{k}\right )\) from the dynamic range \(\mathbb {Z}_{M_{k}}\) can be computed as follows:
where \({\widehat \rho }_{k}\left (X\right )\) is calculated according to Theorem 1,
while
\(\chi _{i,k}^{\left (0\right )}\) and \({\widehat \rho }_{k}^{\left (0\right )}\) are calculated according to (44) and (45), respectively.
$$ \rho_{k}\left( X\right)={\widehat\rho}_{k}\left( X\right)+\delta_{k}\left( X\right), $$
(47)
$$ \delta_{k}\left( X\right)=\left|\chi_{0}+{\widehat\chi}_{0}\right|_{2}, $$
(48)
$$ {\widehat\chi}_{0}=\left|\sum\limits_{i=1}^{k}{{\chi}_{i,k}^{\left( 0\right)}}+{\widehat\rho}_{k}^{\left( 0\right)}\right|_{2}, $$
The proof of this theorem follows directly from equations (38)–(45), taking into account the fact that \(\left |a-b\right |_{2}=\left |a+b\right |_{2}\)\(\left (a,b\in \mathbb {Z}\right )\).
Following Theorem 2, the transition from non-redundant to minimally redundant modular coding allows replacing in (32) the rank correction \({\varDelta }_{k}\left (X\right )\) requiring time-consuming calculations by a trivially calculated two-value attribute \(\delta _{k}\left (X\right )\in \left \{0,1\right \}\).
At the same time, as can be easily seen, the calculations according to (47) are reduced to a set of quickly implemented modular operations modulo mk (the calculation of the inexact rank \({\widehat \rho }_{k}\left (X\right )\)) and modulo m0 (the calculation of the correction \(\delta _{k}\left (X\right )\)). Also, as follows from the equation (48), the calculation of \({\widehat \rho }_{k}\left (X\right )\) can be performed in parallel with the calculation of the value
whose correction by using \({\widehat \rho }_{k}^{\left (0\right )}\) in the final stage of the calculation gives us the resulting value of \(\delta _{k}\left (X\right )\).
$$ \delta_{0}=\left|\chi_{0}+\sum\limits_{i=1}^{k}{\chi_{i,k}^{\left( 0\right)}}\right|_{2}, $$
Thus, in the minimally redundant RNS the calculation of the rank \(\rho _{k}\left (X\right )\) is carried out exceptionally merely within the scope of the modular computational process, which can be easily implemented, for example, by using high-performance lookup-table methods in \(T_{k}=\left \lceil \log _{2}{k}\right \rceil \) modular clock cycles.
Because of the use of minimum-redundancy residue code, the complexity of calculating the rank \(\rho _{k}\left (X\right )\) is significantly reduced in comparison with non-redundant analogs. First of all, this is due to the need to perform the modular addition operations only with respect to the one k th modulus mk instead of the k-moduli set \(\left \{m_{1}, m_{2},\dots ,m_{k}\right \}\) in the case of conventional non-redundant RNS. Therefore, the computational complexity decreases from \(O\left (k^{2}\right )\) to \(O\left (k\right )\) modular operations.
Accordingly, the number of required lookup tables to store the sets of residues is also reduced from \(O\left (k^{2}\right )\) to \(O\left (k\right )\).
The corresponding costs for calculating the rank \(\rho _{k}\left (X\right )\) in minimally redundant RNS are
lookup tables and
modular addition operations, including the correction of the inexact rank \({\widehat \rho }_{k}\left (X\right )\) by two-valued correction \(\delta _{k}\left (X\right )\).
$$ {N}_{LUT}^{\left( R\right)}=k $$
(49)
$$ {N}_{MO}^{\left( R\right)}=k $$
(50)
Here it is assumed that to the i th lookup table one records a pair of residues \(\left \langle R_{i,k}\left (\chi _{i}\right ), \chi _{i,k}^{\left (0\right )}\right \rangle \), which calculated according to equations (18), (19), and (44), \(R_{i,k}\left (\chi _{i}\right )\in \mathbb {Z}_{m_{k}}\), \(\chi _{i,k}^{\left (0\right )}\in \mathbb {Z}_{2}\) \(\left (i=1,2,\dots ,k\right )\). Thus, the bit-width of the used lookup tables is \(l=\left \lceil \log _{2}{m_{k}}\right \rceil +1\).
As can be seen, the use of minimally redundant RNS results in a significant reduction of computational costs both in terms of required modular addition operations and lookup tables relative to the non-redundant RNS. The reduction factors of the computational complexity of calculating the rank \(\rho _{k}\left (X\right )\) in minimally redundant RNS compared to conventional non-redundant RNS are represented by the following fractions
for the number of required lookup tables (see (36) and (49)), and
for the number of modular addition operations (see (37) and (50)).
$$ C_{LUT}=\frac{N_{LUT}}{{N}_{LUT}^{\left( R\right)}}=\frac{k^{2}+k-2}{2k} $$
(51)
$$ C_{MO}=\frac{N_{MO}}{{N}_{MO}^{\left( R\right)}}=\frac{k^{2}+5k-10}{2k} $$
(52)
Equations (51) and (52) show that the reduction factors CLUT and CMO increase with the number k of non-redundant moduli \(m_{1},m_{2},\dots ,m_{k}\) asymptotically approaching the threshold k/2.
For example, take the number k of non-redundant RNS moduli as a multiple of 5:
Then for the reduction factors (51) and (52), we have the following values depending on the number of modules k, respectively:
and
$$ k = 5,\ 10,\ 15,\ 20,\ 25,\ 30. $$
$$ C_{LUT} = 2.8,\ 5.4,\ 7.93,\ 10.45,\ 12.96,\ 15.47 $$
$$ C_{MO} = 4.0,\ 7.0,\ 9.67,\ 12.25,\ 14.8,\ 17.33. $$
Thus, the proposed approach for the rank calculation in minimally redundant RNS with the length k of primary residue code from 5 to 30 digits compared to conventional non-redundant RNS allows us to reduce the computational costs by 2.8 – 15.47 times in terms of lookup table memory and by 4.0 – 17.33 times in terms of required modular addition operations.
Below we give the numerical examples, which demonstrate the calculation of the integer value of the number \(X=\left (\chi _{1},\chi _{2},\dots ,\chi _{k}\right )\) based on the CRT-form (7) in the proposed minimally redundant RNS.
Let us consider the RNS with the moduli m1 = 5, m2 = 7, m3 = 9, and m4 = 11 from Example 1, taking into account the excess modulus m0 = 2.
Example 2
Suppose we wish to calculate the rank \(\rho _{k}\left (X\right )\) of the number X = 2 having the minimally redundant residue code \(\left (0,2,2,2,2\right )\).
First, the residues \(R_{i,4}\left (\chi _{i}\right )\) and \({\chi }_{i,4}^{\left (0\right )}\) \(\left (i=1,2,3,4\right )\) are calculated according to (18), (19), and (44), respectively. As a result, we have
$$ \begin{array}{@{}rcl@{}} &&R_{1,4}\left( \chi_{1}\right)=\left|-\left|2\cdot2\right|_{5}\cdot9\right|_{11}=8,\\ &&R_{2,4}\left( \chi_{2}\right)=\left|-\left|5\cdot2\right|_{7}\cdot8\right|_{11}=9,\\ &&R_{3,4}\left( \chi_{3}\right)=\left|-\left|8\cdot2\right|_{9}\cdot5\right|_{11}=9,\\ &&R_{4,4}\left( \chi_{4}\right)=\left|2\cdot8\right|_{11}=5\\ \end{array} $$
and
$$ \begin{array}{@{}rcl@{}} &{\chi}_{1,4}^{\left( 0\right)}=\left|\left|2\cdot2\right|_{5}\right|_{2}=0,\\ &{\chi}_{2,4}^{\left( 0\right)}=\left|\left|3\cdot2\right|_{7}\right|_{2}=0,\\ &{\chi}_{3,4}^{\left( 0\right)}=\left|\left|4\cdot2\right|_{9}\right|_{2}=0,\\ &{\chi}_{4,4}^{\left( 0\right)}=\left|\left|8\cdot2\right|_{11}\right|_{2}=1.\\ \end{array} $$
It can be noted that the normalized residues \(\chi _{l,4} \ \left (l=1,2,3,4\right )\) (see (5)) take on the values 4, 6, 8, 5, respectively.
Further, we find the number of occurred overflows when summing the residues of the set \(\langle R_{1,4}\left (\chi _{1}\right ),R_{2,4}\left (\chi _{2}\right ),R_{3,4}\left (\chi _{3}\right ),R_{4,4}\left (\chi _{4}\right )\rangle \) = 〈8,9,9,5〉 modulo m4 = 11, i.e., we calculate the inexact rank
Therefore,
$$ {\widehat\rho}_{4}\left( X\right)=\left\lfloor {\left( 8+9+9+5\right)}/{11} \right\rfloor=\left\lfloor{31}/{11}\right\rfloor=2. $$
$$ {\widehat\rho}_{4}^{\left( 0\right)}={\left|{\widehat\rho}_{4}\left( X\right)\right|}_{2}=0. $$
Then, taking into account the fact that χ0 = 0, according to (48), we calculate two-valued correction
As a result, we get the rank
$$ \delta_{4}\left( X\right)=\left|0+\left( 0+0+0+1\right)+0\right|_{2}=\left|1\right|_{2}=1. $$
$$ \rho_{4}\left( X\right)={\widehat\rho}_{4}\left( X\right)+\delta_{4}\left( X\right)=2+1=3. $$
To verify the obtained result, using the CRT-form (7), by analogy with Example 1, we find
$$ \begin{array}{@{}rcl@{}} X&=& \sum\limits_{i=1}^{4}{M_{i,4}\chi_{i,4}}-\rho_{4}\left( X\right)M_{4} \\ &=& 693\cdot 4+ 495\cdot 6+ 385\cdot 8+ 315\cdot 5-3\cdot 3465 \\ &=& 10397-10395=2. \end{array} $$
Example 3
Suppose we wish to calculate the rank \(\rho _{k}\left (X\right )\) of the number X = M4 − 2 = 3463, which is represented by the minimum-redundancy residue code \(\left (1,3,5,7,9\right )\).
Similar to Example 2, we compute
and
$$ \begin{array}{@{}rcl@{}} &&R_{1,4}\left( \chi_{1}\right)=\left|-\left|2\cdot3\right|_{5}\cdot9\right|_{11}=2,\\ &&R_{2,4}\left( \chi_{2}\right)=\left|-\left|5\cdot5\right|_{7}\cdot8\right|_{11}=1,\\ &&R_{3,4}\left( \chi_{3}\right)=\left|-\left|8\cdot7\right|_{9}\cdot5\right|_{11}=1,\\ &&R_{4,4}\left( \chi_{4}\right)=\left|9\cdot8\right|_{11}=6\\ \end{array} $$
$$ \begin{array}{@{}rcl@{}} &{\chi}_{1,4}^{\left( 0\right)}=\left|\left|2\cdot3\right|_{5}\right|_{2}=1,\\ &{\chi}_{2,4}^{\left( 0\right)}=\left|\left|3\cdot5\right|_{7}\right|_{2}=1,\\ &{\chi}_{3,4}^{\left( 0\right)}=\left|\left|4\cdot7\right|_{9}\right|_{2}=1,\\ &{\chi}_{4,4}^{\left( 0\right)}=\left|\left|8\cdot9\right|_{11}\right|_{2}=0.\\ \end{array} $$
As can be seen, the normalized residues \(\chi _{l,4} \ \left (l=1,2,3,4\right )\) (see (5)) take on the values 1, 1, 1, 6, respectively.
We find the inexact rank \({\widehat \rho }_{4}\left (X\right )\) by counting the occurred overflows when summing the residues of the set \(\langle R_{1,4}\left (\chi _{1}\right ),R_{2,4}\left (\chi _{2}),R_{3,4}(\chi _{3}\right ),R_{4,4}\left (\chi _{4}\right )\rangle =\ \) 〈2,1,1,6〉 modulo m4 = 11, i.e.,
$$ {\widehat\rho}_{4}\left( X\right)=\left\lfloor{\left( 2+1+1+6\right)}/{11}\right\rfloor=\left\lfloor{10}/{11}\right\rfloor=0. $$
Hence,
$$ {\widehat\rho}_{4}^{\left( 0\right)}=\left|{\widehat\rho}_{4}\left( X\right)\right|_{2}=0. $$
Since χ0 = 1, it follows from (48) that the correction
$$ \delta_{4}\left( X\right)=\left|1+\left( 1+1+1+0\right)+0\right|_{2}=\left|4\right|_{2}=0. $$
Thus, in this case
$$ \rho_{4}\left( X\right)={\widehat\rho}_{4}\left( X\right)=0. $$
To verify the obtained value, according to (7), we get
$$ \begin{array}{@{}rcl@{}} X&=& \sum\limits_{i=1}^{4}{M_{i,4}\chi_{i,4}}-\rho_{4}\left( X\right)M_{4} \\ &=& 693\cdot 1+ 495\cdot1+ 385\cdot1+ 315\cdot6-0\cdot 3465 \\ &=& 3463. \end{array} $$
As it follows from Example 2 and Example 3, the use of minimally redundant RNS allows us to significantly optimize the calculation of the rank \({\widehat \rho }_{k}\left (X\right )\), and correspondingly, the execution of non-modular procedures based on the use of the CRT. First of all, it caused by the utmost simplicity of forming the two-value characteristic \(\delta _{k}\left (X\right )\), as well as the modular structure of the basic equation for calculating the inexact rank \({\widehat \rho }_{k}\left (X\right )\) (see Theorem 1). This circumstance allows us to radically simplify the calculation of the rank \(\rho _{k}\left (X\right )\) and, consequently, to construct faster and optimal in cost variants of RNS arithmetic.
Therefore, the proposed version of minimally redundant RNS takes priority compared to non-redundant RNS concerning the optimization of the implementation of non-modular procedures on the base of the CRT algorithm.
7 Conclusions
In this paper, we have shown that the use of minimum-redundancy residue code can allow the construction of efficient RNS implementations based on the CRT due to optimizing the calculation of the rank \(\rho _{k}\left (X\right )\), a principal positional characteristic in RNS arithmetic.
We investigated the structure of the rank \(\rho _{k}\left (X\right )\) and proposed a novel method for calculating the correction \({\varDelta }_{k}\left (X\right )\) to the inexact rank \({\widehat \rho }_{k}\left (X\right )\). This method is based on the fact that the correction \({\varDelta }_{k}\left (X\right )\) is a two-value number \(({\varDelta }_{k}\left (X\right )\in \left \{0,1\right \})\) in the case when the RNS moduli \(m_{1},m_{2},\dots ,m_{k}\) are chosen according to the rule of Theorem 1. That allows us to reduce the computational complexity of calculating the rank \(\rho _{k}\left (X\right )\) from \(O\left (k^{2}\right )\) to \(O\left (k\right )\) owing to introducing the minimum redundancy of the residue code by adding the redundant residue modulo m0 = 2, which, in essence, is the parity of the RNS number X.
The reduction factors of the computational complexity of the rank calculation in minimally redundant RNS compared to non-redundant RNS increase with the number k of RNS moduli asymptotically approaching the threshold k/2. For example, the use of minimally redundant RNS with the length k of primary residue code from 5 to 30 digits enables us to reduce the computational costs by 2.8–15.47 times in terms of lookup table memory and by 4.0 – 17.33 times in terms of required modular addition operations.
Therefore, the proposed minimally redundant RNS takes priority in the field of rapid calculations, especially in the case of the large RNS dynamic range, for example, for implementing various complicated algorithms of digital signal processing and cryptography. Thus, the examined approach to implementation of the CRT algorithm in minimally redundant RNS coincides with the vector of the development of modern methods and algorithms of high-performance and high-accuracy computing.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.