mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2017-12-12, 13:34   #1
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

32·163 Posts
Default 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
alpertron is offline   Reply With Quote
Old 2017-12-12, 13:57   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

Quote:
Originally Posted by alpertron View Post

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
science_man_88 is online now   Reply With Quote
Old 2017-12-12, 14:03   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

32×163 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2017-12-12, 14:12   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

Quote:
Originally Posted by alpertron View Post
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
science_man_88 is online now   Reply With Quote
Old 2017-12-12, 14:19   #5
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

5×353 Posts
Default

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.
Nick is offline   Reply With Quote
Old 2017-12-12, 14:29   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

146710 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2017-12-12, 14:34   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

22×401 Posts
Default

Quote:
Originally Posted by alpertron View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2017-12-12, 14:42   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts
Default

Quote:
Originally Posted by alpertron View Post
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
science_man_88 is online now   Reply With Quote
Old 2017-12-12, 14:43   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

32·163 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2017-12-12, 14:59   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts
Default

Quote:
Originally Posted by alpertron View Post
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
science_man_88 is online now   Reply With Quote
Old 2017-12-12, 15:11   #11
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

64416 Posts
Default

Quote:
Originally Posted by alpertron View Post
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
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Complexity of Chinese Remainder Theorem carpetpool Miscellaneous Math 4 2017-02-09 19:26
Basic Number Theory 6: functions and the Chinese Remainder Theorem Nick Number Theory Discussion Group 4 2016-10-31 22:26
Chinese Remainder Problem ShiningArcanine Math 2 2007-11-17 10:01
Implementing Chinese Remainder Theorem in C ShiningArcanine Software 3 2007-11-17 05:55
Card Sorting Probability 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔