mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Riesel Prime Search

Reply
 
Thread Tools
Old 2007-01-15, 14:24   #1
Thomas11
 
Thomas11's Avatar
 
Feb 2003

3×5×127 Posts
Default 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
Thomas11 is offline   Reply With Quote
Old 2007-01-15, 15:11   #2
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

2×1,811 Posts
Default

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
Kosmaj is offline   Reply With Quote
Old 2007-01-15, 20:09   #3
Cruelty
 
Cruelty's Avatar
 
May 2005

31228 Posts
Default

Is there any chance to prepare this sieve software for any value of "k"?
Cruelty is offline   Reply With Quote
Old 2007-01-16, 06:34   #4
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

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.
geoff is offline   Reply With Quote
Old 2007-01-16, 21:28   #5
amphoria
 
amphoria's Avatar
 
"Dave"
Sep 2005
UK

2×19×73 Posts
Default

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
amphoria is offline   Reply With Quote
Old 2007-01-17, 07:14   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23×191 Posts
Default

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
VBCurtis is online now   Reply With Quote
Old 2007-01-18, 05:37   #7
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

100100001012 Posts
Default

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.
geoff is offline   Reply With Quote
Old 2007-01-18, 08:21   #8
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23×191 Posts
Default

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
VBCurtis is online now   Reply With Quote
Old 2007-01-19, 10:12   #9
Cruelty
 
Cruelty's Avatar
 
May 2005

2×809 Posts
Default

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
Cruelty is offline   Reply With Quote
Old 2007-01-19, 17:13   #10
amphoria
 
amphoria's Avatar
 
"Dave"
Sep 2005
UK

1010110101102 Posts
Default

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.
amphoria is offline   Reply With Quote
Old 2007-01-19, 23:18   #11
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

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.
geoff is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 20:31.

Sun Oct 25 20:31:45 UTC 2020 up 45 days, 17:42, 0 users, load averages: 2.19, 1.66, 1.59

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.