Best complexity of parity/comparison in the Residue Number System

Let:

• $$\left\{m_1, ~...~, m_k\right\}$$ be a set of coprime natural numbers,
• $$M=\prod_{i=1}^{k} m_i$$
• $$X$$ be a natural integer, such that $$X < M$$

Then $$X$$ can be expressed in the Residue Number System as:

$$X={\left(x_1, ~...~, x_k\right)}_{RNS\left(m_1, ~...~, m_k\right)}~.$$

Where $$\forall_{m_i} \left[\left(x_i \equiv X \mod m_i\right) ~~~ \wedge ~~~0 \le x_i < m_i \right]$$.

There are a plethora of papers attacking the problem of parity/magnitude comparison in Residue Number Systems; however many of these papers are focused on chip-depth or shaving large constants off of chip-area. I am finding it difficult to decipher if there are any exact algorithms that run faster than full binary reconstruction, which takes $$\sim \mathcal{O}(k^2)$$ time. (For simplicty/brevity, I am assuming small $$m_i$$, and constant-time modulo-multiplication/addition of each RNS "digit").

Most of the papers' novelties lie in some seeming "gimmick", but no real complexity decrease; examples of results:

• Fast inexact parity algorithms (usually work terribly when $$X < \sqrt{M}$$, or $$|X| \ll |M|$$, where $$\left|n\right|=\text{size of }n=\left\lceil\log_2n\right\rceil$$)
• Algorithms that work quickly "most of the time"; ie. they use an inexact algorithm, and then the full CRT reconstruction or equivalent in the worst case
• The circuit they present competes with some other paper's circuit by some constant, or area/depth tradeoff, but makes no complexity advance
• Full CRT reconstruction of $$X$$, perhaps using some trick to save some constants
• Reconstruct/convert to another number system (including binary) where parity/comparison is easy, but:
• this conversion/reconstruction takes $$\sim \mathcal{O}(k^2)$$ time,
• or it runs in $$\sim \mathcal{O}(k)$$, time but with $$k$$ processors,
• or it runs in $$\sim \mathcal{O}(k)$$ time because that is the depth of the circuit, but this is not algorithmic complexity,
• or it reuses previous components that must be there for RNS multiplication (saving circuit space), but still runs in $$\sim \mathcal{O}(k^2)$$ sequential-time, or $$\sim \mathcal{O}(k)$$ parallel-time
• Using a "core" function which basically boils down to a constant-trimmed-CRT, or an approximate CRT
• Using special moduli, makes individual operations simpler, but parity complexity stays the same
• Using special moduli, but limited number of moduli or can't have small $$m_i$$
• Base extension, saves some constant or allows parallel-ness, but complexity is again $$\sim \mathcal{O}(k^2)$$ sequential-time, or $$\sim \mathcal{O}(k)$$ parallel-time (for multiplication)
• Redundant moduli, but maintaining the redundant moduli takes $$\sim \mathcal{O}(k^2)$$ sequential-time, or $$\sim \mathcal{O}(k)$$ parallel-time
• Using lookup tables to reduce depth of some parity, no complexity improvement

Many of the papers do not address complexity at all, or do not address sequential complexity, or even more confusingly, some state the depth/parallel complexity without being precise that it is not sequential; until you read and decipher the entire paper, and discover it yourself.

Bottom line

What are the best sequential, worst-case, complexity results in RNS* for exact parity checking or magnitude comparison?

*Results for RNS-like system would also be interesting, including special moduli sets

More background info:

Multiplication of two numbers in the same RNS base is simply pointwise modulo multiplication of the two numbers (this can be approximately linear time). However, overflow detection is difficult (it is difficult with addition as well). Multiplication seems much simpler, but parity and magnitude comparison of two numbers seems much more difficult. Magnitude comparison is simply determining which of two numbers is greater, $$X \stackrel{?}{<} Y$$, given only their RNS form with the same RNS bases. Parity is simply deciding if a number, $$X={\left(x_1, ~...~, x_k\right)}_{RNS\left(m_1, ~...~, m_k\right)}$$ is even or odd (obviously, $$X$$ is not given, only its RNS form). An interesting thing is that magnitude comparison and parity are related: If you were able to compute parity, then you can do comparison. To do comparison with parity, you do $$(X - Y)$$ (in RNS), and if it underflows, the parity will be unexpected. That is, normally, assuming $$p(X) = X \mod 2, ~~~ p(X) \in \{0,1\}$$ is the parity function, $$p(X-Y) \equiv p(X) + p(Y) \mod 2$$. However, if it underflows, it will wrap around to $$M-1$$. Therefore if the parity is off after $$X-Y$$, you know that $$Y > X$$.

• Can you define what you mean by "magnitude comparison"? Is it the following? Given $x$ and $y$ expressed in RNS, determine whether $x<y$ holds or not. – D.W. Oct 23 '13 at 22:52
• By parity, I assume you mean the following: given $x$ in RNS, determine whether the number of bits set in the binary representation of $x$ is even or odd. Is that correct? Just want to make sure I've got the problem statement correct.... – D.W. Oct 23 '13 at 22:54
• @D.W. Magnitude comparison is like you describe. Parity is simply if $X$ is even or odd. – Realz Slaw Oct 23 '13 at 23:10
• @D.W. if you were able to compute parity, then you can do comparison: you do $(X - Y)$, and if it underflows, the parity will be unexpected. That is, normally, assuming $p(X) = X \mod 2, ~~~ p(X) \in \{0,1\}$ is the parity function, $p(X-Y) \equiv p(X) + p(Y) \mod 2$. However, if it underflows, it will wrap around to $M-1$. Therefore if the parity is off after $X-Y$, you know that $Y > X$. – Realz Slaw Oct 23 '13 at 23:15