mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-02-08, 10:12   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×53 Posts
Post Complexity of Chinese Remainder Theorem

What is the average running time on the Chinese remainder theorem for solving congruence modulo primes up to p_n where p_n is the nth prime?

e.g. the complexity of solving congruence set
{[x, 2], [x_2, 3},
{[x, 2], [x_2, 3], [x_3, 5]},
{[x, 2], [x_2, 3], [x_3, 5], [x_4, 7]},....
{[x, 2], [x_2, 3], [x_3, 5], [x_4, 7]......, [x_n, p_n]}

For the purpose of generating fairy large random numbers, what is the complexity at solving congruence sets modulo the first n primes?

Programs such as ntheory, PARI/GP should handle this but I'm unaware of the timing. It takes a few seconds for primes p < 1669, but what about timing when solving congruence sets mod primes p < 38677?
carpetpool is offline   Reply With Quote
Old 2017-02-08, 13:01   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts
Default

Quote:
Originally Posted by carpetpool View Post
What is the average running time on the Chinese remainder theorem for solving congruence modulo primes up to p_n where p_n is the nth prime?

e.g. the complexity of solving congruence set
{[x, 2], [x_2, 3},
{[x, 2], [x_2, 3], [x_3, 5]},
{[x, 2], [x_2, 3], [x_3, 5], [x_4, 7]},....
{[x, 2], [x_2, 3], [x_3, 5], [x_4, 7]......, [x_n, p_n]}

For the purpose of generating fairy large random numbers, what is the complexity at solving congruence sets modulo the first n primes?

Programs such as ntheory, PARI/GP should handle this but I'm unaware of the timing. It takes a few seconds for primes p < 1669, but what about timing when solving congruence sets mod primes p < 38677?
Code:
my(a=primes([2,38677]),b=vector(#a,i,Mod(random(a[i]-1),a[i])));fold((x,y)->chinese(x,y),b)
runs in 782 ms. on my machine roughly and
Code:
my(a=primes([2,38677*2]),b=vector(#a,i,Mod(random(a[i]-1),a[i])));fold((x,y)->chinese(x,y),b)
is 3,970 ms.

and
Code:
my(a=primes([2,38677*4]),b=vector(#a,i,Mod(random(a[i]-1),a[i])));fold((x,y)->chinese(x,y),b)
is about 19,470 ms. and this includes generating the primes etc. so roughly speaking every time you double the top prime used you times by 5 the time needed. okay the ratio seems to start falling more the higher you go for me personally. 38677 *8 gave a time of about 1 min, 30.172 seconds , note I haven't done too much testing at each level to get a random sample.

Last fiddled with by science_man_88 on 2017-02-08 at 13:07 Reason: adding more information.
science_man_88 is offline   Reply With Quote
Old 2017-02-08, 15:37   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

58916 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Code:
my(a=primes([2,38677]),b=vector(#a,i,Mod(random(a[i]-1),a[i])));fold((x,y)->chinese(x,y),b)
runs in 782 ms. on my machine roughly and
Code:
my(a=primes([2,38677*2]),b=vector(#a,i,Mod(random(a[i]-1),a[i])));fold((x,y)->chinese(x,y),b)
is 3,970 ms.

and
Code:
my(a=primes([2,38677*4]),b=vector(#a,i,Mod(random(a[i]-1),a[i])));fold((x,y)->chinese(x,y),b)
is about 19,470 ms.
You can do it much faster. It is a known problem, and solvable in almost linear time with binary splitting.

In vector v give the problem: if you need x==r[i] mod m[i] for i=1..L, then v=[Mod(r[1],m[1]),...,Mod(r[L],m[L])]. The solution (if exists) will be f(v), note that this solves the general problem, so we don't assume that the m[] values are pairwise coprime.

Code:
allocatemem(10^9)
default(primelimit,10^7)

f(v)={local(L,mid,j);L=length(v);
if(L==1,return(v[1]));
if(L==2,return(chinese(v[1],v[2])));
mid=L\2;return(chinese(f(vecextract(v,vector(mid,j,j))),f(vecextract(v,vector(L-mid,j,mid+j)))))}

v=[Mod(0,2),Mod(1,3),Mod(4,5),Mod(2,7)];
f(v)

test(s)={a=primes([2,s]);b=vector(#a,i,Mod(random(a[i]),a[i]));return(f(b))}

#
test(38677);
test(2*38677);
test(4*38677);
test(8*38677);
test(16*38677);
test(32*38677);
test(64*38677);
test(128*38677);
test(256*38677);
it has given (in the first line the solution of the sample CRT problem)
Code:
? %4 = Mod(184, 210)                                                                                                                  
? time = 11 ms.                                                                                                                                
? time = 23 ms.                                                                                                                                
? time = 51 ms.
? time = 113 ms.
? time = 267 ms.
? time = 646 ms.
? time = 1,533 ms.
? time = 3,736 ms.
? time = 8,924 ms.
R. Gerbicz is offline   Reply With Quote
Old 2017-02-09, 10:30   #4
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

101110111002 Posts
Default

If you are interested in the theory, look up Garner's algorithm in Prof. Knuth's "The Art of Computer Programming" (volume 2).
Nick is offline   Reply With Quote
Old 2017-02-09, 19:26   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

Since Perl/ntheory was mentioned... The GMP code for my chinese function does a recursive function to what Robert mentions, though I chunk by splitting in 8 rather than 2. The times for large numbers of inputs are nearly identical to his simple test function on my machine.

But ... my non-GMP chinese function takes surprisingly long to return indicating overflow. It comes down to, of all things, sorting the moduli. I just fixed that. It now goes to GMP with little overhead even with hundreds of thousands of pairs.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sorting on chinese remainder theorem alpertron Math 23 2017-12-15 16:46
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
division/remainder algorithm (trial factoring) TheJudger Math 4 2007-10-18 19:01

All times are UTC. The time now is 06:49.

Fri Nov 27 06:49:20 UTC 2020 up 78 days, 4 hrs, 4 users, load averages: 0.79, 1.23, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.