4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.