Скачать или смотреть Strange counters (Residue Number Systems)

This video explains Residue Number Systems (RNS).

The usual way to define RNS is as follows:
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 for addition and multiplication 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.

Regarding the comment at 13:52:

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-M*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.


Music ID: 1YYBAL9DCELLYTIS