20070115, 14:24  #1 
Feb 2003
1,907 Posts 
new sieving software
I just want to draw your attention to a new sieving software made by goeff, available at:
http://www.geocities.com/g_w_reynolds/321sieve/rps/ As a spinoff of his recent 321sieve he prepared two specialized sieves for k=15 and k=17. I had some test runs and found both variants faster than NewPGen. To give some timings for sieving 0.1B of k=15 on a 2.4GHz Opteron: Code:
NewPGen 2.82: 83 sec rps15sievei686: 53 sec rps15sievep4: 49 sec rps15sievek8: 46 sec Code:
NewPGen 2.82: 210 sec rps15sievep4: 124 sec For k=17 I've got the following figures (I tested only the Opteron): Code:
NewPGen 2.82: 47 sec rps17sievei686: 42 sec rps17sievep4: 39 sec rps17sievek8: 37 sec Last fiddled with by Thomas11 on 20070115 at 14:28 
20070115, 15:11  #2 
Nov 2003
E26_{16} Posts 
Thanks to geoff for his new sieving software.
I did a test on k=17, n=400k2M, p=5523.65523.7bn using Athlon2000 (1.67GHz clock): Code:
NewPGen 2.81: 69 sec rps15sievei586: 57 sec OTOH, I'm not sure can we sieve k=15 and k=17 together, because k=15 is sieved to 3M but k=17 only to 2M. Do the exponent ranges have to be the same? Last fiddled with by Kosmaj on 20070115 at 15:16 
20070115, 20:09  #3 
May 2005
2·809 Posts 
Is there any chance to prepare this sieve software for any value of "k"?

20070116, 06:34  #4  
Mar 2003
New Zealand
13×89 Posts 
Quote:
Quote:
I suspect the 64bit code could be made quite a bit faster, the k8 build doesn't currently make best use of SSE2. 

20070116, 21:28  #5 
"Dave"
Sep 2005
UK
2·19·73 Posts 
I have done some speed testing on various processors. The following numbers are kp/sec resulting from sieving k=15 from p=20T for 1B.
Code:
NewPGen rpssieve Pentium4 740 1234 PentiumM 821 1430 Core Duo 1058 1918 Core 2 Duo 1460 2666 Last fiddled with by amphoria on 20070116 at 21:29 
20070117, 07:14  #6 
"Curtis"
Feb 2005
Riverside, CA
2^{2}×3^{2}×5^{3} Posts 
Ok, Geoff, I'm interested. I am sieving two very long projects: k=99 up to n=4M (sieve currently at 11T, planning to go to 70T or so)
Also k=13. Just started this sieve, but figured I'd set it up for the long haul, so sieving 1M to 10M. Initial rough forecast for sieve depth on the order of 175T. I assume k=99 would benefit more from this speedup, as it is rather slow in NewPgen. I currently sieve in windows, but could install SUSE on the sieving box if the code is linuxonly. I would only need some guidance for setting up two instances on a Core2Duo (both for 99) My understanding of NewPGen is that for fixedk sieving, sieve speed decreases with the square root of nrange. Is this also true for your program? Curtis 
20070118, 05:37  #7  
Mar 2003
New Zealand
13×89 Posts 
Quote:
Quote:
Quote:


20070118, 08:21  #8 
"Curtis"
Feb 2005
Riverside, CA
2^{2}·3^{2}·5^{3} Posts 
Thanks, geoff!
I'm downloading openSUSE 10.264 tonight, so I should have a working linux install this week. I needed motivation to get it up, your possible future code was sufficient to get me going. If you get a chance to build a 99 sieve, don't worry about the windows binary. (13 would only run on windows.. but I don't want to be greedy) thanks again. Curtis 
20070119, 10:12  #9 
May 2005
652_{16} Posts 
I am sieving k=25 and several other "k" in the range 1M<n<2M using ksieve2m, afterwards (probably 6 months from now) I may verify the results with the new sieving software, if there is any Win32 binary

20070119, 17:13  #10 
"Dave"
Sep 2005
UK
2×19×73 Posts 
I have just finished testing k=15 from p=20.0T to 20.1T using rps15sieve and it found exactly the same 7 factors as newpgen.
I am also testing sr2sieve (the multik version of rpssieve) against prothsieve. So far it has found exactly the same factors as prothsieve and is almost 50% faster. I'll report further when this is complete. 
20070119, 23:18  #11 
Mar 2003
New Zealand
13·89 Posts 
I hope to get around to making the sieve work for a single sequence k*b^n+/1 with any values of k and b, but until that happens, here is a brief guide to converting rpssieve to work with different k values:
Consider the sequence k*2^n1: Let X be the squarefree part of k. [X=core(k) in pari/GP] If there are any odd n terms then let Y=2*X, otherwise let Y=X. If Y=1 (mod 4) then let Z=Y, otherwise let Z=2*Y. If Z < 64 then the sieve can be converted just by changing the following values in rpssieve.h: K_TERM: Set to k MASK_MOD: Set to Z as calculated above. ODD_TERMS: Set to 1 if there are any odd n terms, 0 otherwise. EVEN_TERMS: Set to 1 if there are any even n terms, 0 otherwise. LMASK_T: Set to uint32_t if Z < 32, uint64_t otherwise. LMASK_C: Set to UINT32_C if Z < 32, UINT64_C otherwise. EVEN_MASK: Set to 0 if there are no even n terms, otherwise set to LMASK_C(U) ODD_MASK: Set to 0 if there are no odd n terms, otherwise set to LMASK_C(V) U is a bitmap with bit i set iff Legendre(X,2*i+1) = +1. V is a bitmap with bit j set iff Legendre(2*X,2*j+1) = +1. To calculate U and V in pari/GP: U=0;for(i=0,Z1,if(kronecker(X,2*i+1)==1,U+=2^i));U V=0;for(j=0,Z1,if(kronecker(2*X,2*j+1)==1,V+=2^i));V Set RANGE_SIZE in primes.h to be a multiple of 2*Z. [Optional] If the values for MASK_MOD, ODD_MASK or EVEN_MASK are wrong then factors will be missed, the sieve will run slow, or both. Test against NewPGen or srsieve output. You need to test a range that produces at least a thousand factors to be reasonably sure that none are missed. For some reason the pentium4 build is noticeably faster when compiled with GCC version 3.4. Other 32bit builds are faster compiled with GCC version 4.1. I don't know about 64bit builds. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Generalized Cullen/Woodall Sieving Software  rogue  And now for something completely different  13  20141229 19:11 
Suggestion for new sieving software  ATH  Factoring  3  20120404 13:03 
Line sieving vs. lattice sieving  JHansen  NFSNET Discussion  9  20100609 19:25 
Sieving Software  lavalamp  Software  10  20071020 23:07 
Software  TTn  PSearch  0  20040504 13:16 