Parity check and magnitude comparison in Residue Number Systems

Let

• $\{m_1,...,m_t\}$ be a set of relatively coprime integers
• $M=\prod_{i=1}^tm_i$ the range of this system
• $X$ an integer such that $X \in [0,M-1]$

This forms a Residue Number System and every integer $X$ can be uniquely represented in RNS format as $(x_1,\dots,x_t)$, where $x_i = X\bmod m_i, \forall i\in[0,t]$.

One can add,subtract,multiply efficiently in RNS by adding,subtracting,multiplying modulo $m_i$ in parallel the corresponding RNS digits as in

$X\otimes Y=(x_1,\dots,x_t)\otimes(y_1,\cdots,y_t)=(x_1 \otimes y_1,\cdots,x_t \otimes y_t)$, where $\otimes=(+,-,\times) \bmod m_i$

There are various operations though that are not efficient in RNS, like parity check or magnitude comparison. I've encountered an interesting algorithm for parity check directly in RNS and I would like to take advantage of it to perform sign detection (in fact checking whether the result of $X-Y$ is negative or not). The idea comes from another topic where I quote exactly the part I don't understand:

"...one can compute $X-Y$ and if it underflows, the parity will be unexpected. That is, if $p(X)=X \bmod 2$, $p(X)\in\{0,1\}$ is the parity function, then $p(X−Y) \equiv p(X)+p(Y) \bmod 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$".

What is meant by "parity if off?" How can I check an underflow by just checking the parities?

The "parity check" of a number $X$ is 0 or 1 according to whether $X$ is even or odd. In other words, the parity of $X$ is $X \bmod 2$. We are assuming that you have a way to compute the parity of $X$, from the RNS representation of $X$. Let $p(X)$ denote the parity of $X$, i.e., $p(X) = X \bmod 2$.

Now let's suppose $X,Y$ are integers in $[0,M-1]$ that we have stored in RNS representation, and let's look at what happens when we subtract the RNS representations. If $X$ is represented as $(x_1,\dots,x_t)$ and $Y$ is represented as $(y_1,\dots,y_t)$, the result of the subtraction operation will be the RNS representation $(z_1,\dots,z_t)$ where $z_i = x_i-y_i \bmod m_i$.

What number $Z$ is $(z_1,\dots,z_t)$ the representation of? Well, if $X\ge Y$, then $Z$ will be $X-Y$. But -- and here is the key point -- if $X<Y$, then $Z$ will not be $X-Y$, as $X-Y$ is negative and RNS can only represent numbers in the range $[0,M-1]$. Instead, what will happen is that we'll have $Z \equiv X-Y \pmod M$. Therefore, if $X<Y$, we'll have $Z = X-Y+M$... which is not the same as $X-Y$.

If $X\ge Y$, then $X-Y \ge 0$ and we say that the subtraction $X-Y$ doesn't underflow; in this case, $p(Z)$ will be $p(X)$ minus $p(Y)$ modulo 2. In other words, if $X \ge Y$, we will have $Z=X-Y$ and therefore using the properties of modulo-2 arithmetic we have

$$p(Z) = p(X-Y) \equiv X-Y \equiv p(X)-p(Y) \pmod 2.$$

In contrast, if $X < Y$, then $X-Y < 0$ and we say that the subtraction $X-Y$ underflows. In this case, $p(Z)$ will be $p(X)$ minus $p(Y)$ plus 1 modulo 2. In other words, if $X<Y$, we will have $Z=X-Y+M$ and therefore

$$p(Z) = p(X-Y+M) \equiv X-Y+M \equiv p(X)-p(Y)+1 \pmod 2.$$

Here I have used the fact that $M$ will always be odd, so $p(M)=1$.

This gives you a way to check whether $X\le Y$, given RNS representations for $X,Y$: you subtract them to get a RNS representation of some integer $Z$, and then test whether $p(Z) \stackrel{?}{\equiv} p(X)-p(Y) \pmod 2$.

The key observation is that "subtraction" of RNS representations is not actually computing the subtraction (of integers). Rather, it is computing the subtraction modulo $M$. If the result of the subtraction is in the range $[0,M-1]$, that's equivalent to subtraction in the integers. But if subtraction underflows, it's different.

This might look mysterious, but it's not as unfamiliar as it might feel. If you use twos-complement arithmetic on 32-bit integers, that is basically doing modulo $2^{32}$ arithmetic: addition of 32-bit ints is not actually addition (of integers), but addition modulo $2^{32}$. In other words, with twos-complement addition of 32-bit integers, the results of arithmetic operations "wrap around" modulo $2^{32}$. RNS is just like that, except that it "wraps around" modulo $M$ instead of modulo $2^{32}$.

"parity is off" means "parity is wrong", i.e., the parity doesn't match what you'd expect to get, if subtraction of RNS representations behaved like subtraction of integers.

• I should mention, I think that none of the moduli are allowed to be $2$. Oct 25 '17 at 17:56