20171212, 13:34  #1 
Aug 2002
Buenos Aires, Argentina
2·17·43 Posts 
Sorting on chinese remainder theorem
In some of my applets, I compute the values modulo the prime factors of some composite device and then reconstruct the values using CRT.
For instance x = 2, 4 (mod 7), x = 3, 9 (mod 13) and x = 6, 19 (mod 37). So my applet computes: x1 = 2 (mod 7), x1 = 3 (mod 13), x1 = 6 (mod 37) > x1 = 1745 (mod 3367) x2 = 2 (mod 7), x2 = 3 (mod 13), x2 = 19 (mod 37) > x2 = 3201 (mod 3367) x3 = 2 (mod 7), x3 = 9 (mod 13), x3 = 6 (mod 37) > x3 = 191 (mod 3367) x4 = 2 (mod 7), x4 = 9 (mod 13), x4 = 19 (mod 37) > x4 = 1647 (mod 3367) x5 = 4 (mod 7), x5 = 3 (mod 13), x5 = 6 (mod 37) > x5 = 1264 (mod 3367) x6 = 4 (mod 7), x6 = 3 (mod 13), x6 = 19 (mod 37) > x6 = 2720 (mod 3367) x7 = 4 (mod 7), x7 = 9 (mod 13), x7 = 6 (mod 37) > x7 = 3077 (mod 3367) x8 = 4 (mod 7), x8 = 9 (mod 13), x8 = 19 (mod 37) > x8 = 1166 (mod 3367) Is there any way to generate the 8 values of x (mod 7*13*37) sorted without having to generate all values of x using CRT and then sorting them? Last fiddled with by alpertron on 20171212 at 13:51 
20171212, 13:57  #2  
"Forget I exist"
Jul 2009
Dumbassville
3×2,801 Posts 
Quote:
Last fiddled with by science_man_88 on 20171212 at 14:43 

20171212, 14:03  #3 
Aug 2002
Buenos Aires, Argentina
2×17×43 Posts 
If it helps, in this case x = 1745 + 1456 * a + 1813 * b + 2886 * c (mod 3367) where the values of a, b and c can be zero or one.

20171212, 14:12  #4 
"Forget I exist"
Jul 2009
Dumbassville
3×2,801 Posts 
well that would show when they wrap around since 1745+1813 > 3367 and similarly with 1745+2886>3367 so these will wrap around and since the excess is less than 1745 they will produce lower values. and since 1456+1745<3367 it will not wrap so it only produces the higher value. that covers 1/4 of all cases ( 1/3 if you count the all 0's case trivially being the same).
Last fiddled with by science_man_88 on 20171212 at 14:13 
20171212, 14:19  #5 
Dec 2012
The Netherlands
6E5_{16} Posts 
With small integers like this, you could simply take each number in turn in the order you want them and test what the remainder is on division by 7,13 and 37.
The deeper mathematical answer is that the integers modulo 3367 are not ordered. I would tend to think of them as 1683 to +1683, but in theory you could start anywhere. 
20171212, 14:29  #6 
Aug 2002
Buenos Aires, Argentina
2×17×43 Posts 
This is a very small example so it is easy to understand, but the numbers can have hundreds of digits and the number of solutions can be 2^{n} for n between 15 and 20, so the idea is to generate the first chunk of results and a "Continue" button so the user can see the next chunk.
That means that I cannot generate all solutions and sort them. Last fiddled with by alpertron on 20171212 at 14:32 
20171212, 14:34  #7  
"Robert Gerbicz"
Oct 2005
Hungary
2×3×263 Posts 
Quote:


20171212, 14:42  #8  
"Forget I exist"
Jul 2009
Dumbassville
3·2,801 Posts 
Quote:
and same for the rest. what you seem to want is a sorting by least positive value equivalence. Last fiddled with by science_man_88 on 20171212 at 14:43 

20171212, 14:43  #9 
Aug 2002
Buenos Aires, Argentina
2×17×43 Posts 
Unfortunately there is not enough memory to hold all 2^{n} results found with CRT because this is an application that runs inside a Web browser and the memory is limited. The problem is not the sorting time (calculating the modular values of x is more expensive), but the amount of memory.

20171212, 14:59  #10  
"Forget I exist"
Jul 2009
Dumbassville
20323_{8} Posts 
Quote:
Last fiddled with by science_man_88 on 20171212 at 15:04 

20171212, 15:11  #11  
"Robert Gerbicz"
Oct 2005
Hungary
2×3×263 Posts 
Quote:
res=sum(i=1,k,c[i]*M/p[i]), where M=p[1]*...*p[k], if you have t[i] possibilities for x mod p[i] then you have exactly(!) t[i] possibilities for c[i] mod p[i], you need to reduce res mod M, because the above can be bigger than M. With a simple loop using small memory you can generate each res value, if you need the residues between index L and H then use binary search on res values to get the Lth residue and the Hth residue. Here there is an overhead, because you recompute all residue multiple times but you are using small memory, with more memory: you can guess the ith res: it will be around i*M/cnt, if you have cnt=t[1]*..*t[k], save the residue if you are close to this, and use sorting on these to get the Lth residue with only expected only one generating, plus one more generation for the printing. A better using more memory use meetinthemiddle alg: make two groups of primes, then each res=C1*U+C2*V, where U*V=M, and for C1 you have cnt1=2^(n\2) for C2 you have cnt2=2^((n+1)/2) possibilities. This res is still not reduced, it is res or resM, make a heap of size (at most) 2*cnt1, with this you can generate all of them in fly. First in the heap the terms are C1[i]*U+C2[0]*V and C1[i]*U+C2[j]*VM (if this last is existing), where C1[i]*U+C2[j]*V is the first term that is at least M for the given i index. Maybe it is a little complicated but should be working, notice also that not in all cases there is a new term if you pop a term from the heap. Last fiddled with by R. Gerbicz on 20171212 at 15:14 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Complexity of Chinese Remainder Theorem  carpetpool  Miscellaneous Math  4  20170209 19:26 
Basic Number Theory 6: functions and the Chinese Remainder Theorem  Nick  Number Theory Discussion Group  4  20161031 22:26 
Chinese Remainder Problem  ShiningArcanine  Math  2  20071117 10:01 
Implementing Chinese Remainder Theorem in C  ShiningArcanine  Software  3  20071117 05:55 
Card Sorting Probability  MiniGeek  Math  13  20070113 15:31 