PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : Sieving : Choosing sieve range

Author Message
Profile S@NL - FilmFreakProject donor
Avatar
Send message
Joined: 29 Nov 05
Posts: 58
ID: 1587
Credit: 3,290,496
RAC: 0
321 LLR Silver: Earned 100,000 credits (235,773)PPS LLR Gold: Earned 500,000 credits (512,812)SR5 LLR Gold: Earned 500,000 credits (508,431)SGS LLR Bronze: Earned 10,000 credits (71,624)TRP LLR Bronze: Earned 10,000 credits (82,218)Woodall LLR Bronze: Earned 10,000 credits (10,077)PPS Sieve Amethyst: Earned 1,000,000 credits (1,755,489)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (90,725)
Message 7310 - Posted: 19 Oct 2007 | 10:53:05 UTC
Last modified: 19 Oct 2007 | 11:00:26 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
Project administrator
Avatar
Send message
Joined: 22 Jun 05
Posts: 2653
ID: 1
Credit: 102,368,713
RAC: 82,384
321 LLR Silver: Earned 100,000 credits (104,475)Cullen LLR Silver: Earned 100,000 credits (291,372)ESP LLR Bronze: Earned 10,000 credits (18,156)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (15,259)PPS LLR Amethyst: Earned 1,000,000 credits (1,320,329)PSP LLR Silver: Earned 100,000 credits (116,517)SoB LLR Silver: Earned 100,000 credits (282,655)SR5 LLR Bronze: Earned 10,000 credits (18,916)SGS LLR Silver: Earned 100,000 credits (193,600)TPS LLR (retired) Silver: Earned 100,000 credits (111,607)TRP LLR Emerald: Earned 50,000,000 credits (76,495,083)Woodall LLR Silver: Earned 100,000 credits (101,463)321 Sieve (suspended) Silver: Earned 100,000 credits (201,501)Cullen/Woodall Sieve Silver: Earned 100,000 credits (337,061)Generalized Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (14,200)PPS Sieve Jade: Earned 10,000,000 credits (10,004,155)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (200,232)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,453,872)AP 26/27 Amethyst: Earned 1,000,000 credits (1,880,022)GFN Amethyst: Earned 1,000,000 credits (1,621,146)WW (retired) Turquoise: Earned 5,000,000 credits (6,456,000)PSA Bronze: Earned 10,000 credits (97,541)
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 :)
____________

Profile S@NL - FilmFreakProject donor
Avatar
Send message
Joined: 29 Nov 05
Posts: 58
ID: 1587
Credit: 3,290,496
RAC: 0
321 LLR Silver: Earned 100,000 credits (235,773)PPS LLR Gold: Earned 500,000 credits (512,812)SR5 LLR Gold: Earned 500,000 credits (508,431)SGS LLR Bronze: Earned 10,000 credits (71,624)TRP LLR Bronze: Earned 10,000 credits (82,218)Woodall LLR Bronze: Earned 10,000 credits (10,077)PPS Sieve Amethyst: Earned 1,000,000 credits (1,755,489)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (90,725)
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

geoffProject donor
Volunteer developer
Send message
Joined: 3 Aug 07
Posts: 99
ID: 10427
Credit: 343,437
RAC: 0
TRP Sieve (suspended) Bronze: Earned 10,000 credits (57,150)PSA Silver: Earned 100,000 credits (271,962)
Message 7317 - Posted: 19 Oct 2007 | 21:29:51 UTC - in response to Message 7310.
Last modified: 19 Oct 2007 | 21:43:46 UTC

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

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2023 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 1.87, 2.15, 2.46
Generated 4 Jun 2023 | 0:59:35 UTC