## Other

drummers-lowrise

Message boards : Sieving : Choosing sieve range

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
S@NL - FilmFreak

Joined: 29 Nov 05
Posts: 58
ID: 1587
Credit: 3,290,496
RAC: 0

Message 7310 - Posted: 19 Oct 2007 | 10:53:05 UTC

Would it be possible to choose your own sieve range. Right now you can only get ranges of 2e7, i think you could increase speed quite a bit by choosing a larger range like 1e8, which is 5x as large, but it will only take 3x or 4x as much time to sieve.

Geoff@http://www.rieselsieve.com/forum/viewtopic.php?p=11517 wrote:
The sieve algorithm takes time roughly proportional to the square root of the number of k sieved at once. Sieving the 67 Riesel k together is more than 8 times more efficient than sieving each one seperately.

The time is also roughly proportional to the square root of the range of n sieved, so sieving 0M-20M is about 4.5 times more efficient than sieving 4M-5M.

Above is about srsieve, not gcwsieve, but i think the algorithms are roughly the same.

____________
Life is short and meaningless, unless you make the best of it.
http://server.by014.net/~weezepoe

Rytis
Volunteer moderator

Joined: 22 Jun 05
Posts: 2653
ID: 1
Credit: 102,368,713
RAC: 82,384

Message 7311 - Posted: 19 Oct 2007 | 13:01:18 UTC - in response to Message 7310.

Workunit duration does not have any effect in sieve speed. Number to be sieved can be imagined as a matrix, where you have sieve range in one axis and sieve depth in another one. By selecting bigger sieve range (which is currently 5M-10M) you get a speed increase. By selecting bigger sieve depth range you get no speed increase.

I hope it's clear, it seems complicated when I read what I wrote :)
____________

S@NL - FilmFreak

Joined: 29 Nov 05
Posts: 58
ID: 1587
Credit: 3,290,496
RAC: 0

Message 7316 - Posted: 19 Oct 2007 | 18:07:30 UTC - in response to Message 7311.

Workunit duration does not have any effect in sieve speed. Number to be sieved can be imagined as a matrix, where you have sieve range in one axis and sieve depth in another one. By selecting bigger sieve range (which is currently 5M-10M) you get a speed increase. By selecting bigger sieve depth range you get no speed increase.

I hope it's clear, it seems complicated when I read what I wrote :)

It is clear indeed, I was confusing n and p in the message I quoted in p|k*2^n+-1.

But you need to sieve the p-range as well, because you only want the primes in that range and see if they divide any number in the sieve_WOO_1191169882.sieveinput_in file. This might be done more efficiently for a bigger p-range, but I don't know if this matters very much or just seconds
____________
Life is short and meaningless, unless you make the best of it.
http://server.by014.net/~weezepoe

geoff
Volunteer developer

Joined: 3 Aug 07
Posts: 99
ID: 10427
Credit: 343,437
RAC: 0

Message 7317 - Posted: 19 Oct 2007 | 21:29:51 UTC - in response to Message 7310.

Above is about srsieve, not gcwsieve, but i think the algorithms are roughly the same.

sr2sieve and gcwsieve algorithms are quite different, but neither will gain much from sieving a larger p range.

Both algorithms work like this at the top-most level:

for each prime p in [pmin, pmax]
do some work ...

The amount of work done for each p is large relative to the time taken to find each p using the Sieve of Eratosthenes.

Message boards : Sieving : Choosing sieve range