new sieving software

Thomas11 · 2007-01-15, 14:24

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)...

Kosmaj · 2007-01-15, 15:11

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?

Cruelty · 2007-01-15, 20:09

Is there any chance to prepare this sieve software for any value of "k"?

geoff · 2007-01-16, 06:34

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.

amphoria · 2007-01-16, 21:28

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.

VBCurtis · 2007-01-17, 07:14

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

geoff · 2007-01-18, 05:37

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.

VBCurtis · 2007-01-18, 08:21

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

Cruelty · 2007-01-19, 10:12

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

amphoria · 2007-01-19, 17:13

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.

geoff · 2007-01-19, 23:18

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.

2007-01-15, 14:24	#1
Thomas11 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 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 3622₁₀ 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-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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Generalized Cullen/Woodall Sieving Software	rogue	And now for something completely different	13	2014-12-29 19:11
Suggestion for new sieving software	ATH	Factoring	3	2012-04-04 13:03
Line sieving vs. lattice sieving	JHansen	NFSNET Discussion	9	2010-06-09 19:25
Sieving Software	lavalamp	Software	10	2007-10-20 23:07
Software	TTn	PSearch	0	2004-05-04 13:16

2007-01-15, 20:09	#3
Cruelty May 2005 2³×7×29 Posts	Is there any chance to prepare this sieve software for any value of "k"?

2007-01-17, 07:14	#6
VBCurtis "Curtis" Feb 2005 Riverside, CA 3·1,543 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, 08:21	#8
VBCurtis "Curtis" Feb 2005 Riverside, CA 3·1,543 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 2³×7×29 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

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 13·89 Posts	I hope to get around to making the sieve work for a single sequence kb^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 k2^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=2X, otherwise let Y=X. If Y=1 (mod 4) then let Z=Y, otherwise let Z=2Y. 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,2i+1) = +1. V is a bitmap with bit j set iff Legendre(2X,2j+1) = +1. To calculate U and V in pari/GP: U=0;for(i=0,Z-1,if(kronecker(X,2i+1)==1,U+=2^i));U V=0;for(j=0,Z-1,if(kronecker(2X,2j+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.