mersenneforum.org new sieving software
 Register FAQ Search Today's Posts Mark Forums Read

 2007-01-15, 14:24 #1 Thomas11     Feb 2003 111011100012 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 spin-off 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 rps15sieve-i686: 53 sec rps15sieve-p4: 49 sec rps15sieve-k8: 46 sec And for a 2.4GHz P4: Code: NewPGen 2.82: 210 sec rps15sieve-p4: 124 sec (I never was aware that for sieving the difference between Intel and AMD machines is so extreme!) For k=17 I've got the following figures (I tested only the Opteron): Code: NewPGen 2.82: 47 sec rps17sieve-i686: 42 sec rps17sieve-p4: 39 sec rps17sieve-k8: 37 sec While the improvements are not very significant for the k=17 case (due to the fact that there are no odd exponents for k=17), we note a tremendous increase of the sieving speed for k=15! Please do your own timings and tests (especialy on the Intel Core2 cpus)... Last fiddled with by Thomas11 on 2007-01-15 at 14:28
 2007-01-15, 15:11 #2 Kosmaj     Nov 2003 2×1,811 Posts Thanks to geoff for his new sieving software. I did a test on k=17, n=400k-2M, p=5523.6-5523.7bn using Athlon-2000 (1.67GHz clock): Code: NewPGen 2.81: 69 sec rps15sieve-i586: 57 sec Two composites found as expected. But I suggest we do some more tests before switching to it. 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 2007-01-15 at 15:16
 2007-01-15, 20:09 #3 Cruelty     May 2005 161810 Posts Is there any chance to prepare this sieve software for any value of "k"?
2007-01-16, 06:34   #4
geoff

Mar 2003
New Zealand

13·89 Posts

Quote:
 Originally Posted by Kosmaj 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?
You can still sieve them together using sr2sieve, but the speed will be the same as for sieving both at the higher 3M limit. If you do this then you should also check the speed of Proth sieve and JJsieve, they may be faster depending on the number of k in the sieve and the range of n being tested.

Quote:
 Originally Posted by Cruelty Is there any chance to prepare this sieve software for any value of "k"?
Yes, any k < 2^64 is possible with a few changes, although the smaller the squarefree part of k is, the easier it is to do and the more efficient the sieve will be.

I suspect the 64-bit code could be made quite a bit faster, the k8 build doesn't currently make best use of SSE2.

 2007-01-16, 21:28 #5 amphoria     "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 Pentium-4 740 1234 Pentium-M 821 1430 Core Duo 1058 1918 Core 2 Duo 1460 2666 As Kosmaj suggests we now need to do some quality testing against NewPGen. Last fiddled with by amphoria on 2007-01-16 at 21:29
 2007-01-17, 07:14 #6 VBCurtis     "Curtis" Feb 2005 Riverside, CA 423710 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 linux-only. I would only need some guidance for setting up two instances on a Core2Duo (both for 99) My understanding of NewPGen is that for fixed-k sieving, sieve speed decreases with the square root of n-range. Is this also true for your program? -Curtis
2007-01-18, 05:37   #7
geoff

Mar 2003
New Zealand

13×89 Posts

Quote:
 Originally Posted by VBCurtis 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.
These two should both be quite easy to do, the squarefree parts are both < 16. I'll get back to you.

Quote:
 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 linux-only. I would only need some guidance for setting up two instances on a Core2Duo (both for 99)
I can create binaries for Windows by cross-compiling from Linux with the mingw compiler, but for 32-bit platforms only. The mingw compiler doesn't yet support 64-bit mode.

Quote:
 My understanding of NewPGen is that for fixed-k sieving, sieve speed decreases with the square root of n-range. Is this also true for your program?
For the single k sieve, yes.

 2007-01-18, 08:21 #8 VBCurtis     "Curtis" Feb 2005 Riverside, CA 10000100011012 Posts Thanks, geoff! I'm downloading openSUSE 10.2-64 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
 2007-01-19, 10:12 #9 Cruelty     May 2005 110010100102 Posts I am sieving k=25 and several other "k" in the range 1M
 2007-01-19, 17:13 #10 amphoria     "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 multi-k 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.
 2007-01-19, 23:18 #11 geoff     Mar 2003 New Zealand 48516 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^n-1: Let X be the square-free 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,Z-1,if(kronecker(X,2*i+1)==1,U+=2^i));U V=0;for(j=0,Z-1,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 32-bit builds are faster compiled with GCC version 4.1. I don't know about 64-bit builds.

 Similar Threads Thread Thread Starter Forum Replies Last Post rogue And now for something completely different 13 2014-12-29 19:11 ATH Factoring 3 2012-04-04 13:03 JHansen NFSNET Discussion 9 2010-06-09 19:25 lavalamp Software 10 2007-10-20 23:07 TTn PSearch 0 2004-05-04 13:16

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

Wed Aug 5 08:42:49 UTC 2020 up 19 days, 4:29, 1 user, load averages: 2.45, 2.12, 1.85