Sieve Coordination Thread
Hi guys. The public sieve is... well... public :):
http://www.seventeenorbust.com/sieve/
Most of the info you need to get started is there.
The community should start at p = 25 billion. I'm gonna finish the range below that myself.
I'd recommend 25 billion wide p ranges since the n range is so wide (n = 3 - 20 million).
i. e.
first person: 25 - 50 billion
next person: 50 - 75 billion
next person: 75 - 100 billion
etc...
Don't let what you experience during the k=4847 sieving decieve you... sieving 17 million n-wide takes a lot longer than 1 million.
That said, it won't be 17 times slower. Paul Jobling managed to make SoBSieve several times faster than NewPGen was. This implementation is even faster than the private 2.71 beta that a few of you have.
If 25 billion wide don't make sense, change it but don't do a low p range unless you're SURE you can do it. It is very important that we get to a decent sieve level before the server starts assigning n-values above n=3 million.
If you are using a slow computer or are new and unsure if you want to do sieving, please reserve a range above 1 trillion for now.
In the future, I hope to make something on the sieve page to reserve ranges without using this forum but for now please coordinate using this thread exclusively.
One last reminder: Make sure you're logged into the SB site if you want to have it remember that you submitted the results (for future stats purposes). The sieve submission is really simple. That site again is:
http://www.seventeenorbust.com/sieve/
There will be an anouncement on the site about it tomorrow. Email me if you run into any problems.
Happy sieving folks. This should be interesting! :)
-Louie
Behaviour of alpha, and speed as a function of p
The cost of testing a prime is almost certainly
time(generating the next prime)
+#bigsteps * time(bigstep)
+#babysteps * time(babystep) * #ks
The initial term, sieving for p, should be negligible, and shouldn't make too much difference. I'm sure Paul's sieve uses a n.loglog(n) algorithm, so it will slow down slightly as the p range increases, but there will be fewer primes to test, so the total time to do a p range should remain flat. (In my own sieves they tend to decrease.)
The big steps are modular multiplications and writing entries into some kind of hashing structure. These are quite slow.
The baby steps are either simple halvings or doublings, and lookups into the previously created hash table. These are very fast, assuming you can stay within the cache. However, you can't! Nonetheless they're still quite quick.
Both of the above depend on the exact machine architecture being used. However, one that's faster for the big steps will almost certainly also be faster for the baby steps too. The exact ratio may vary though.
To perform a discrete log (which is what fixed-k sieving is), the product of the number of big steps and baby steps must exceed the n range.
So all in all the cost is
C0 + C1*B + C2/B
Where B is the cost of the big step, and C0,C1,C2 are constants.
Now while this appears to shoot off to infinity, is does have quite a broad area where it will be quite flat.
For example, some times for my own particular discrete log with various alphas:
0.6 1m54.690s
0.8 1m51.680s
1.0 1m49.290s
1.2 1m49.300s
1.4 1m48.690s
1.6 1m49.040s
1.8 1m50.010s
2.0 1m50.680s
2.2 1m51.660s
2.4 1m51.730s
2.6 1m54.270s
2.8 1m55.940s
3.0 1m56.720s
3.2 1m58.240s
3.4 1m59.830s
Now while it might appear obvious the 1.4-1.5 would be best for the above run, times of _identical_ tests across multiple runs can vary by up to about 2% or more, much more than the half-percent separating the times above. I get the feeling that it's more sensitive to the state of the cache than it is to the alpha parameter. (The jump between 2.4's 1:51 and 2.6's 1:54 is an example of this difference, I'm sure.)
So, in summary - don't worry to much about the exact value of alpha, as long as you're within a range of the theoretically perfect value your rate won't vary hugely.
Phil