This video explains Residue Number Systems (RNS) using mechanical counters.
The abstract way to define RNS
We choose n integers (a1,a2,…,an) greater than 1 such that they are relatively prime (no shared prime factors). The Chinese Remainder Theorem says that each number x in the range 0…a1*a2*…*an has a unique set of residues (x%a1,x%a2,…,x%an).
The proof that addition and multiplication works as in the video is as follows:
Say a number x has x%5 = n. So x=5a + n for some integer a.
Similarly if y has y%5 = m, then y = 5b + m.
So x + y = 5a + 5b + n + m. And (x + y) % 5 will cause all the multiples of 5 to drop, and we are left just with (n + m) % 5.
Similarly for multiplication, we’ll get x * y = 25ab + 5ma + 5nb + nm and again % 5 will leave just (nm) % 5.
Obtaining the number from the RNS representation
At time 13:52 in the video we show the three basic counters showing (1,0,0), (0,1,0), and (0,0,1). Figuring out which number they represent allows us to find out the value of any counter.
Let’s start with the (5,7,3) counter showing (1,0,0).
We are looking for a number x such that x%5=1 and x%7=0 and x%3=0. Satisfying the last two requirements is easy: x=7*3=21 will obviously satisfy x%7=x%3=0. In this case, it also satisfies x%5=1, but this is a coincidence.
Now the (5,7,3) counter showing (0,1,0).
Again, x=5*3=15 will satisfy x%5=x%3=0. And again, we’re lucky to have x%7=1.
Finally, the (5,7,3) counter showing (0,0,1). Here, x=5*7=35 satisfies x%5=x%7=0. But we’re out of luck: x%3=2 and not 1 as we need. We know however that to satisfy x%5=x%7=0 then x must be a multiple of 35. In the range 0…105 there is only one more option: x=2*35=70, which satisfies x%3=1 as well.
Generally however, with larger moduli, searching like this can be tedious. So here’s the general, efficient algorithm:
Let M be the size of the wheel that shows 1. And N1,N2,…,Nk be the sizes of the wheels that show 0, and N=N1*N2* . . . *Nk their product.
M and N share no prime factors. According to a known result in number theory, because M and N share no prime factors, then the equation N*a+M*b=1 has a solution where a and b are integers. Note that the equation N*a+M*b=1 is in regular arithmetic, not modular arithmetic.
For example, if M=5 and N=21, then 21a+5b=1 can be solved with a=1 and b=-4.
Also, there’s an efficient algorithm, called the Extended Euclidean Algorithm, that is given N and M and it finds a and b.
This is useful for us, because x=N*a satisfies all the requirements we need:
- N is the product of the sizes N1, N2,..,Nk Therefore x%N1=(N*a)%N1=0, and similarly x%N2=x%N3= . . . =0.
- Rearranging the terms, we get that x=N*a=1-N*b. This means that x%M=(1-M*b)%M=1, (because the %M operation drops all multiples of M), and so the size-M wheel shows 1.