mersenneforum.org > Math Sorting on chinese remainder theorem
 Register FAQ Search Today's Posts Mark Forums Read

 2017-12-12, 13:34 #1 alpertron     Aug 2002 Buenos Aires, Argentina 32·163 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 2017-12-12 at 13:51
2017-12-12, 13:57   #2
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 Originally Posted by alpertron 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?
well other than that last pair of results choosing ones with gcd ==1 in the remainders, seems to fairly well be the highest result of each other pair ( maybe there's a pattern to when that won't be the case).

Last fiddled with by science_man_88 on 2017-12-12 at 14:43

 2017-12-12, 14:03 #3 alpertron     Aug 2002 Buenos Aires, Argentina 32×163 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.
2017-12-12, 14:12   #4
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 Originally Posted by alpertron 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.
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 2017-12-12 at 14:13

 2017-12-12, 14:19 #5 Nick     Dec 2012 The Netherlands 5×353 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.
 2017-12-12, 14:29 #6 alpertron     Aug 2002 Buenos Aires, Argentina 146710 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 2n 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 2017-12-12 at 14:32
2017-12-12, 14:34   #7
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

22×401 Posts

Quote:
 Originally Posted by alpertron 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). 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?
Ofcourse that is a very small example, so not very interesting what you are doing here (quicksort or bubble sort etc. or other algorithm). For a larger problem use buckets, say in your example calculate the remainders with CRT, and put the r residue to the (r>>8) -th bucket, with this we are expecting <1 hit per bucket, so you can get close to a linear algorithm.

2017-12-12, 14:42   #8
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by alpertron 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 2n for n between 15 and 20.
I semi understand what you want, but I also understand Nick's point. the point being that the integers mod a value don't act like a well ordered set. for your small example we have:

$\ldots\equiv-1622\equiv1745\equiv 5112\equiv\ldots (\bmod 3367)$

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 2017-12-12 at 14:43

 2017-12-12, 14:43 #9 alpertron     Aug 2002 Buenos Aires, Argentina 32·163 Posts Unfortunately there is not enough memory to hold all 2n 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.
2017-12-12, 14:59   #10
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts

Quote:
 Originally Posted by alpertron Unfortunately there is not enough memory to hold all 2n 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.
are you useing adding to calculate the CRT result ? you can in theory, but I think since addition and multiplication are similar speeds on modern hardware at last check it won't speed it up.

Last fiddled with by science_man_88 on 2017-12-12 at 15:04

2017-12-12, 15:11   #11
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

64416 Posts

Quote:
 Originally Posted by alpertron That means that I cannot generate all solutions and sort them.
OK, interesting problem, you can write each residue in the following format (it is well known):
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 L-th residue and the H-th 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 i-th 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 L-th residue with only expected only one generating, plus one more generation for the printing.

A better using more memory use meet-in-the-middle 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 res-M, 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]*V-M (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 2017-12-12 at 15:14

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 4 2017-02-09 19:26 Nick Number Theory Discussion Group 4 2016-10-31 22:26 ShiningArcanine Math 2 2007-11-17 10:01 ShiningArcanine Software 3 2007-11-17 05:55 Mini-Geek Math 13 2007-01-13 15:31

All times are UTC. The time now is 12:28.

Thu Dec 8 12:28:00 UTC 2022 up 112 days, 9:56, 0 users, load averages: 0.78, 1.02, 1.01