should all users be sieving...

[dudlio]

At the end of the last sieving thread, MikeH mentioned that we should sieve until sieving becomes as slow as a proth test. In fact, Louie said we should sieve twice as far as that.

Now that we have a new client, SoBSieve, which checks all k's in parallel, and sieving is about to go public, maybe we should discuss an optimal sieving strategy?

For starters, since sieving is done in parallel across n as well, the break-even point depends on how long you expect the project to last. The new client is set up for n=3M to 20M. This is an allocation of 12*17=200 million candidates (k-n pairs).

What percentage can we hope to remove? From the stats page, it looks like we have been sieving out 99.8% of candidates thus far.

[MAD-ness]

While it does make sense to discuss these things, the answer to the question in this thread title is most likely going to be "no."

Sieving is still eliminating numbers far faster than full testing can. With sieving ramping up, we should be able to get pretty far out ahead of the range of n values being assigned by the SoB server.

Also keep in mind that the coordination process is not ready for prime-time, the stats aren't integrated to the point where they will be sufficiently rewarding to the "average" user for sieving, that it requires another client (with a pretty good sized download of results files) and that it adds a lot of additional complexity to the project and the client(s).

That said, at some point it will have to be discussed what the medium and long term plans for sieving are. Other than Louie and perhaps Paul, I am not sure anyone understands the situation well enough to make accurate projections.

[jjjjL]

There are a few people around who understand the sieving issue as well or better than I do. FatPhil and paul.jobling are both very well informed and I would consider what they say to be authoritative on the matter. That said, the answer to "should everyone sieve?" is "no" and here's the major reasons why.

Reasons why people shouldn't want to sieve:

1) The program is not as simple to run as SB
2) The program requires more user intervention to work
3) Coordination requires people to register for this forum
4) No stats (although userid/team is being recorded for future stats)
5) You won't find a prime
6) SobSieve uses 28MB of memory

The real reason people should run SB instead of SoBSieve is a little more subtle:

Running SoBSieve can only find composites. Running SB finds a lot of composites, but it also finds primes too. Finding a prime will eliminate the need for a lot more work than sieving. A number removed by sieving saves us from having to run a single test. A prime for a given k saves us from having to run ALL the tests! This alone is justification for most of the cpu resources to stick with SB, and not sieve. Also, the more time we spend sieving now, the more time we "waste" sieving for that k when a prime is found. If tomorrow, we find a prime for a given k with an n value around 2.5million, then some of the work we do will be unnessisary.

For now, I think a small group of dedicated individuals will be good to do all the sieving. I know some of the people that are doing sieving are doing it on machines they couldn't otherwise run SB. Computers behind proxies come to mind... and computers with no internet connection at all. Running SoBSieve on computers like that is great because you're only increasing productivity.

I'd say that the rule of thumb should pretty much be,

"Don't run SoBSieve on a machine you could be running SB on."

-Louie

[smh]

What percentage can we hope to remove? From the stats page, it looks like we have been sieving out 99.8% of candidates thus far.

There are 12 candidates, and we're sieving a range of 17*10^6 N's, thats a total of 204*10^6 numbers.

The sieve file which is available for download contains over 825.000 numbers to sieve, and is sieved to 5.7*10^9.

I can't find the link right now, but i read somewere that sieving twices as far would elliminate about 3% more candidates.

So that would leave us with about 800.000 nembers when sieved to 12G,........ so thats about 630.000 when sieved upto 3T, which is a bit over 0,3% of the original 204M numbers.

[jwolfe]

Originally posted by smh

I can't find the link right now, but i read somewere that sieving twices as far would elliminate about 3% more candidates.

See the last paragraph of this page .

- Jeff

[MAD-ness]

Thanks for that link jwolfe.

[Cowering]

Back of envelope math.. am I right?

We seem to have n=2-3M seived right now. if 99.8% (listed above) are seived and composite.. that leaves 2000 N's per K, which is 24,000 values to test. Project stats say we did 719 complete tests yesterday. 24,000/719 is about 33.4.

Do we really only have 33 days of N left (lower since more cpus are computing every day)? Will the new SoBSieve get a usable set of N within a month?

[smh]

Originally posted by Cowering
Back of envelope math.. am I right?

Yes

Originally posted by Cowering

We seem to have n=2-3M seived right now. if 99.8% (listed above) are seived and composite.. that leaves 2000 N's per K, which is 24,000 values to test. Project stats say we did 719 complete tests yesterday. 24,000/719 is about 33.4.

Do we really only have 33 days of N left (lower since more cpus are computing every day)? Will the new SoBSieve get a usable set of N within a month?

99,8% is a bit optimistic for the 2-3M range. IIRC for K=4847 it was about 99,6% when sieving over 1T. K's with a lower proth weight remove a bit more candidates, but some are sieved less far (i think). So that will give us 35000 numbers between 2-3M.

OTOH, several thousand already have been tested, so something like 25000 numbers left to test. There are also over 2500 tests assigned already, so between 20 and 25 thousand tests are not assigned yet.

The number of tests per day is slowly decreasing, last week it was over 800. Tests just take longer and longer, and 25 new users each day can't compensate this. (maybe they can, but the "Users active in the last 2 weeks" stays about the same for the last week. So my guess is that it will take a bit longer then your 33 days, probably end of feb, early march.

If sieving hasn't progressed far enough by that time (it won't), the worst that will happen is that a number is proven composite by a prp test instead of a found factor.

NOTE: This are all wild guesses, but probably somewere in the ballpark.

[FatPhil]

Originally posted by smh
The sieve file which is available for download contains over 825.000 numbers to sieve, and is sieved to 5.7*10^9.

Based on the above, there's speculative prediction of the number of candidates remaining after various sieving depths, and corresponding value for the sieving 'rate',at
http://fatphil.org/maths/sierpinski/

Your extrapolation using my previous figure was quite accurate, so there're no real surprised there. However, hopefully people can get more of a feel for how sieving slows down from that table.

Phil