 mersenneforum.org How do you efficiently sieve for prime 3/4-tuples?
 Register FAQ Search Today's Posts Mark Forums Read  2013-07-22, 14:09   #111
Puzzle-Peter

Jun 2009

10101111002 Posts Quote:
 Originally Posted by R. Gerbicz Peter, could you rerun your test, or post the input parameters? It should be the same output file, no matter what was the bound_small_primes. Don't know what would be the error, maybe the new code eliminated that also. Now the code prints more information.
Well, whatever happened last week, I could not reproduce it with the new code. The output file is exactly the same no matter what I use for bound_small_primes. I am now testing 34, 35 and 36 hash_bits. The best value is probably dependent on pmax as the table updates take more time. So once I know the optimal pmax I can try to find the best hash_bits and q_hash_table_update values.   2013-07-22, 15:44 #112 henryzz Just call me Henry   "David" Sep 2007 Liverpool (GMT/BST) 11×557 Posts I think that hash_bits depends on the number of candidates.   2013-07-22, 19:53 #113 R. Gerbicz   "Robert Gerbicz" Oct 2005 Hungary 66216 Posts An impressive fast sieve for a new polynom (the polynom depends on s). With this we avoid all prime divisors less than 50, so we don't need to sieve them and this gives also more survivors in the same range. Set bound_small_primes=0 (or any value <2), so we can forget the magic 2310*10^9 as a multiple of the optimal range. Code: Sieve P(s)+a*Q(s)+c for multiple c values, with fixed s=k*b^n+d; P,Q is polynom. Give k: 66735 Give b: 2 Give n: 503 Give d: -1 Give the degree of the P polynom: 3 Give the 0-th coefficient of P: -4 Give the 1-th coefficient of P: -160 Give the 2-th coefficient of P: -77 Give the 3-th coefficient of P: 1 Give the degree of the Q polynom: 2 Give the 0-th coefficient of Q: 0 Give the 1-th coefficient of Q: -1229779565176982820 Give the 2-th coefficient of Q: -614889782588491410 Give the number of c values for the sieve: 3 0-th c value: 1 1-th c value: -1 2-th c value: 5 Give start and end value for 'a' (in billions)! 0 18 Give the limit for sieving primes (maxp): 20000000000 Give the name of the file to output the numbers! f503_0_18m0.txt Using primes for wheelsieve up to 0 initialization of all small primes done, primepi(1000000000)=50847534 Prime divisors of Q(s) up to 1000000000: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 initialization of residue and inverse array done up to p=1000000000. In wheel sieve there will be 1 different combinations mod 1 Start sieving for a=0..18000000000. 1/1; #candidates=132548913; 683 sec. so far. Sort the 'a' array. Done the sorting. Sieve for large primes. Use hashbits=31 Use M=1;mres=0; Update the hash table...done Update the hash table...done Update the hash table...done Sieved up to 2000000000; #candidates=120087517; time so far=983 sec. Update the hash table...done Update the hash table...done Update the hash table...done Sieved up to 3000000000; #candidates=113514747; time so far=1162 sec. Update the hash table...done Sieved up to 4000000000; #candidates=109140947; time so far=1315 sec. Update the hash table...done Update the hash table...done Sieved up to 5000000000; #candidates=105902833; time so far=1449 sec. Update the hash table...done Sieved up to 6000000000; #candidates=103346841; time so far=1565 sec. Update the hash table...done Sieved up to 7000000000; #candidates=101250528; time so far=1670 sec. Sieved up to 8000000000; #candidates=99484200; time so far=1769 sec. Update the hash table...done Sieved up to 9000000000; #candidates=97960285; time so far=1862 sec. Update the hash table...done Sieved up to 10000000000; #candidates=96621926; time so far=1951 sec. Sieved up to 11000000000; #candidates=95430272; time so far=2035 sec. Update the hash table...done Sieved up to 12000000000; #candidates=94362206; time so far=2118 sec. Sieved up to 13000000000; #candidates=93392244; time so far=2198 sec. Update the hash table...done Sieved up to 14000000000; #candidates=92506805; time so far=2276 sec. Sieved up to 15000000000; #candidates=91692650; time so far=2351 sec. Sieved up to 16000000000; #candidates=90938256; time so far=2424 sec. Update the hash table...done Sieved up to 17000000000; #candidates=90238817; time so far=2497 sec. Sieved up to 18000000000; #candidates=89584547; time so far=2569 sec. Sieved up to 19000000000; #candidates=88972664; time so far=2639 sec. Update the hash table...done Sieved up to 20000000000; #candidates=88396540; time so far=2709 sec. Output the remaining 'a' values to the abc file, wait... Done. Number of remaining candidates=88396540. Completed in 2736 sec. Start with my basic polynom: F(a,s)=-4-6*s-a*s*(s+2)+s^3. Let T=614889782588491410=2*3*5*7*11*..*47, the product of primes less than 50. Choose c for that if N=F(c,s) then gcd((N+1)*(N-1)*(N+5),T)=1 is true. It gives that if a==c mod T, then for N=F(a,s) it results that N-1; N+1 and N+5 is relative prime to T. So choose our polynom F(A*T+c), where A is running. a=A*T+c, plug in this to F(a,s) (replaced s by S): S^3-(A*T+c)*S*(S+2)-6*S-4=(S^3-c*S^2+(-2*c-6)*S-4)+A*(-T*S^2-2*T*S)= =(-4+(-2*c-6)*S-c*S^2+S^3)+A*(-2*T*S-T*S^2) as T=614889782588491410 it means that here all coefficients fits in 63 bits (assuming that c is small). If N=F(A*T+c,S) then (S+2)|N and S|N+4. (in above post there was a typo for this divisibility). Basically this trick works for every P,Q polynom, just not forget that the coefficients should fit in 63 bits, so in some cases for example you can use only the primes up to 37 and not up to 50. We can say that this is half-way between the pure power and primorial sieves. ps. Still working on a new code, it will use multiple cores in sieve. Using OpenMp to distribute the tasks (gcc supports this). Trivial Pari-Gp script to get a good c value for given s: Code: fun(s)={T=614889782588491410;c=0;while(1,c++; N=s^3-c*s*(s+2)-6*s-4;p1=N-1;p2=N+1;p3=N+5;if(gcd(p1*p2*p3,T)==1,return(c)))} then use just the polynom: (-4+(-2*c-6)*S-c*S^2+S^3)+A*(-2*T*S-T*S^2), where A is running. Last fiddled with by R. Gerbicz on 2013-07-22 at 20:05   2013-07-22, 20:00   #114
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

31428 Posts Quote:
 Originally Posted by henryzz I think that hash_bits depends on the number of candidates.
No, but I hope the new code will use the number of candidates and the size of memory (what you give the program) to setup different hashtables.   2013-07-22, 20:21 #115 henryzz Just call me Henry   "David" Sep 2007 Liverpool (GMT/BST) 11·557 Posts Would it be possible to automate that trick? These polys are fiddly enough without having to do this each time. 2310*10^9 was only the magic number for bound_small_primes=11. For bound_small_primes=7 it is 210*10^9 etc.   2013-07-22, 20:58   #116
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·19·43 Posts Quote:
 Originally Posted by henryzz Would it be possible to automate that trick? These polys are fiddly enough without having to do this each time.
That is possible, I'll add that option.

See the entry of PolySieve on http://primes.utm.edu/bios/page.php?id=3934

Last fiddled with by R. Gerbicz on 2013-07-22 at 21:28   2014-01-31, 00:46 #117 henryzz Just call me Henry   "David" Sep 2007 Liverpool (GMT/BST) 17EF16 Posts I had a look at the code again tonight and in post #113 n# is limited by the coefficients of p and q. As far as I can see coeff_p and coeff_q are only used %q which is a lli. coeff_p and coeff_q could be converted to a arbitrary precision number and used with only a small performance penalty. You mentioned a couple of bits of new code in the last few posts. Any news? I have been able to find a good few 11-tuples and smaller. I have found a few 12-tuples but finding them is much harder. I am not getting anywhere near as many candidates for 12-tuples as 11-tuples after sieving.   2014-02-03, 04:06 #118 MattcAnderson   "Matthew Anderson" Dec 2010 Oregon, USA 23×149 Posts Hi people interested in k-tuples, I have been working on this problem as well. I have tabulated the smallest known tuples for several patterns, and submitted it to the Online Encyclopedia of Integer Sequences. Lately, I have been working on the 4 different patterns for 9-tuples. I have a bit of Maple code that works for me. It is linked here - https://oeis.org/A022546 Also, my page on prime constellations - https://sites.google.com/site/primeconstellations/ Regards, Matt   2014-02-04, 19:56   #119
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

11×557 Posts I have modified polysieve such that it uses gmp for the the coefficients of p and q. This has allowed me to use much larger factorials. It is a little slower in the second stage and is currently limited to 512 bits(just needs a recompile).
I also exposed some more parameters to the cmd line(first stage p limit, primes in wheel sieve).
Attached Files polysieve2.zip (13.8 KB, 171 views)   2014-03-17, 15:18   #120
Puzzle-Peter

Jun 2009

22×52×7 Posts Quote:
 Originally Posted by henryzz I have modified polysieve such that it uses gmp for the the coefficients of p and q. This has allowed me to use much larger factorials. It is a little slower in the second stage and is currently limited to 512 bits(just needs a recompile). I also exposed some more parameters to the cmd line(first stage p limit, primes in wheel sieve).
I never programmed C and I'm having problems compiling this. I downloaded gmp.h and managed to modify the include path accordingly. But now I get a lot of "undefined reference" messages for all the mpz_xxx commands. Could anybody please point me to what I need to do? Or provide a 64bit Linux build (static)?   2014-03-17, 15:53 #121 henryzz Just call me Henry   "David" Sep 2007 Liverpool (GMT/BST) 612710 Posts To compile with gmp add -lgmp into the compile string. This is the command I use: gcc -O3 -o polysieve3072_gmp.exe polysieve.c -lgmp The order of the commands can make a difference. The wrong order means the -lgmp won't be detected. Hopefully cygwin and linux will need the same order. The gmp.h you added might interfere.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 And now for something completely different 2 2017-04-28 00:08 fivemack Math 27 2015-12-12 18:42 tapion64 GPU Computing 7 2014-04-10 06:15 Unregistered Information & Answers 2 2010-05-25 20:51 Sloth Prime Sierpinski Project 1 2006-05-10 02:02

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

Thu Jun 1 06:03:05 UTC 2023 up 287 days, 3:31, 0 users, load averages: 0.88, 0.87, 0.85