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

2017-12-13, 23:36   #23
alpertron

Aug 2002
Buenos Aires, Argentina

2·32·83 Posts

Quote:
 Originally Posted by chalsall So that suggests an optimization is possible. Any success with that yet?
I will use the suggestions given on post #11, except the part "you can guess the i-th res: it will be around i*M/cnt," The values can be anywhere in the range 0<m<x.

For example if x1 = 2 (mod mr) and x2 = 3 (mod mr), it is clear that x1 = 2 (mod m) and x2 = 3 (mod m) and these values are a lot less than m1 * m2 * m3 * ... mn.

2017-12-15, 16:46   #24
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by alpertron I have read that threorem S but it is not applicable to this problem, because that theorem works when the values are represented as (a1 mod m1, a2 mod m2, a3 mod m3, etc).

which can then be restated in the form of a line on the x,y plane. as y1=m1*x+a1; y2=m2*x+a2; y3=m3*x+a3 and looking for common natural number y co-ordinates amongst them is what CRT is doing. your main problem is you've turned it all into a non-linear form. edit: and as to your around claim it depends on what's meant by around as 1 pm is close to 12 pm even though 1 is not close to 12. your numeric sort of the positive values is just a sort on the y intercepts of the new lines.

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

 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 TimSorbet Math 13 2007-01-13 15:31

All times are UTC. The time now is 08:56.

Mon Jan 30 08:56:39 UTC 2023 up 165 days, 6:25, 0 users, load averages: 1.05, 0.90, 0.89