TAOCP 3.2.1.1 Exercise 5

Since $0 \le x,y<m$, we have $-(m-1)\le x-y\le m-1.$ Hence $(x-y)\bmod m$ is either $x-y$ or $x-y+m$.

taocpmathematicsalgorithmsvolume-2

Section 3.2.1.1: Choice of Modulus

Exercise 5. [**] $[29]$ Given that $m$ is less than the word size, and that $x$ and $y$ are nonnegative integers less than $m$, show that the difference $(x - y) \bmod m$ may be computed in just four MIX instructions, without requiring any division. What is the best code for the sum $(x + y) \bmod m$?

Verified: yes
Solve time: 1m30s

Since $0 \le x,y<m$, we have

$-(m-1)\le x-y\le m-1.$

Hence $(x-y)\bmod m$ is either $x-y$ or $x-y+m$. A subtraction followed by a test of sign therefore suffices.

The four-instruction code is

LDA  X
SUB  Y
JAN  *+2
ENTA 0,1
ADD  M

After SUB Y, register A contains $x-y$. If $x-y\ge0$, the jump is not taken and the value already equals $(x-y)\bmod m$. If $x-y<0$, control passes to ADD M, giving $x-y+m=(x-y)\bmod m$.

For the sum,

$0\le x+y\le 2m-2,$

so $(x+y)\bmod m$ is either $x+y$ or $x+y-m$. The analogous code is

LDA  X
ADD  Y
CMPA M
JL   *+2
SUB  M

After ADD Y, register A contains $x+y$. If $x+y<m$, the jump is taken and the value is already correct. If $x+y\ge m$, subtracting $m$ yields $x+y-m=(x+y)\bmod m$. ∎