Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
Sieving :
Automated sieving
Author |
Message |
rogueVolunteer developer
 Send message
Joined: 8 Sep 07 Posts: 1256 ID: 12001 Credit: 18,565,548 RAC: 0
 
|
Is there a need for an automated sieving system?
Simply put, a way for a server to maintain a db with clients connecting and getting sieve ranges to work on then returning factors?
It doesn't seem to me that such a thing exists, but that such a thing might provide value. | |
|
|
Yes; could the existing PPS Sieve be adapted?
____________
| |
|
|
Yes, PPS Sieve exists, and from the badge list I can see other nonmanual sieving subprojects were:
321 Sieve
Cullen Woodall Sieve
Generalized Cullen Woodall Sieve
ESP/PSP/SoB Sieve (Previously called the PSP Sieve)
TRP Sieve
/JeppeSN | |
|
|
I could see it being useful for people that try their own searches in private, but otherwise I think PrimeGrid should just put everything onto BOINC.
____________
| |
|
Vato Volunteer tester
 Send message
Joined: 2 Feb 08 Posts: 851 ID: 18447 Credit: 713,746,062 RAC: 1,639,286
                           
|
There will probably always be a case for manual sieving in the early stages, where the sheer number of factors removed is massive!
____________
| |
|
Honza Volunteer moderator Volunteer tester Project scientist Send message
Joined: 15 Aug 05 Posts: 1957 ID: 352 Credit: 6,139,475,826 RAC: 2,271,747
                                      
|
In " Is it technically possible to move factorial and primorial searches to BOINC?" thread, there were two particular questions.
Question #1, how would pfgw need to change to support BOINC?
Question #2, how far has the sieving gone? mfsieve (part of the mtsieve framework), which replaced fpsieve/fsieve/fsievecl, can sieve up to 2^62.
Q1 was addresses, but not #2.
After some digging, both in my memory and on forums, I remember we were doing Primorial and Factorial sieves using manual sieving offline and uploading factor files and later combined them to make candidate list.
Primorial Prime Search Sieving
It was 10-15 years ago, CPU only, no MT.
I don't think I would be able to find original factor files to have better estimate how far was the sieving done.
Got an idea: if we sieve some sample ranges and compare then with candidates on PRPNet, would it give us good estimate?
Both PSieve and MTSieve have GPU versions.
Aren't those app's sieve limit much higher than we have acomplished 10-15 years ago?
This may be viable option...
Question for Mark of whoever is more familiar with MTSieve.
>psievecl.exe -n 4M -N 10M -p 7000G -P 7001G -g 64 -G 8 -W 4 -w 5000
>mfsievecl.exe -n 4M -N 10M -p 7000G -P 7001G -g 64 -G 8 -W 4 -w 5000
PSieve is much faster but gives less factors, comparing to MFSieve.
Any good explanation?
Missing factors or I'm missing something? Or both :-)
____________
My stats | |
|
streamVolunteer moderator Project administrator Volunteer developer Volunteer tester Send message
Joined: 1 Mar 14 Posts: 1033 ID: 301928 Credit: 543,624,271 RAC: 6,563
                         
|
I did some research on factorials recently.
Good:
We don't need PFGW anymore. Pavel wrote new own prime testing program which can do fast DC on factorials and primorials.
Everything else is bad:
Factorials were sieved up to N=1M only. Sieving depth was 10000G (sieving of factorials is very slow). May be it's optimal, may be not, main problem is not here. Need to analyze how much work we have. Considering PG crunching rates, it may happen that project will run out candidates in 2-3 months.
Sieving next range (up 2M) will take time twice as previous sieving. There is no fast algorithm for factorials. Sieving for N=2M means that on each iteration program will calculate factorials up to 2M. It also means that sieving program will, in fact, re-sieve everything up 1M again - even if these tests are not included in sieve file, all these iteration are executed anyway, just no factors reported.
Numbers near N=2M will be as big as current SoB. I.e. even if we'll sieve next range, it'll add only small amount of candidates of reasonable length. Most of new added candidates will be big and not fun to crunch.
| |
|
Honza Volunteer moderator Volunteer tester Project scientist Send message
Joined: 15 Aug 05 Posts: 1957 ID: 352 Credit: 6,139,475,826 RAC: 2,271,747
                                      
|
I did some research on factorials recently.
I was discussing Primorials in previous post.
OK, Factorials then.
Currently sieved up to 10000G for N<1M
IF we want to sieve N (1M-2M) up to P<=10000G, it takes about 10 minutes on decent GPU to do a 1G sieve, about 150G a day.
A single GPU will sieve in ~2 months, right?
(N <1M would be about half the time)
This looks too easy to believe, or comparing to 15 years ago. Yes, it was painfully slow on CPU, it is still slow on CPU but not today's GPU.
If the above is correct, definitely not worth to migrate Factorial/Primorial SIEVE to BOINC.
Manual sieving using reservations should be sufficient.
We would need to test correct parameters for sieving, validate output factor files, have a way to eliminate individual factors files from candidate file etc.
Or we may need to sieve deeper, not 10T but 100T or 1000T
1T - 10 T, expecting 153846 factors
10T - 100T, expecting 142857 factors.
100T - 1000, expecting 133333 factors.
Is the sieving still bad?
Yes, candidates would be quite large.
Around 5.5M digits for 1M factorial and just around current SoB with 11.7M digits for 2M factorial.
It will be a while before we reach that range...and it will look smaller by then :-)
Multithreading available in Pavel's app?
mfsievecl.exe -n 1M -N 2M -p 10000G -P 10001G
mfsievecl v2.0, a program to find factors of multi-factorials
1 warning generated.
GPU primes per worker is 94208
Sieve started: 1e13 < p < 10001e9 with 2000002 terms (1000000 <= n <= 2000000, factorial) (expecting 7 factors)
p=10000107753241, 59.33K p/sec, 1 factors found at 116 sec per factor (last 1 min), 10.8% done. ETC 2022-12-03 12:14
...
p=10000973201209, 59.25K p/sec, 4 factors found at 262 sec per factor (last 9 min), 97.3% done. ETC 2022-12-03 12:14
Sieve completed at p=10001000171753.
CPU time: 530.16 sec. (0.03 sieving) (0.94 cores) GPU time: 547.21 sec.
1999998 terms written to factorial.pfgw
Primes tested: 33410688. Factors found: 4. Remaining terms: 1999998. Time: 563.56 seconds.
____________
My stats | |
|
rogueVolunteer developer
 Send message
Joined: 8 Sep 07 Posts: 1256 ID: 12001 Credit: 18,565,548 RAC: 0
 
|
For n between 1e6 and 2e6 you will likely need to sieve more deeply than 1e15.
I started n!6 earlier this year to 1e6 and I could sieve about 1e13 a month. The removal rate was well below what I would need if I were to test to the max n in the sieve. I stopped sieving at 5e13 and am PRP testing now. I guesstimated that I would need to sieve to about 5e14 to fully sieve the range. Since n! is much larger than n!6, I'm thinking that 2e16 will be closer to optimal sieving depth, but that is just a guess. | |
|
Yves Gallot Volunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 820 ID: 164101 Credit: 305,989,513 RAC: 2,326

|
Or we may need to sieve deeper, not 10T but 100T or 1000T
1T - 10T, expecting 153846 factors
10T - 100T, expecting 142857 factors.
100T - 1000, expecting 133333 factors.
The number of remaining candidates should be computed (or the new factors):
Let nc(p_max) be the number of remaining candidates at p_max, we have
nc(10T) = log(1T) / log(10T) * nc(1T) = 12/13 * nc(1T) = 0.923 * nc(1T)
nc(100T) = 0.857 * nc(1T)
nc(1000T) = 0.8 * nc(1T)
| |
|
Honza Volunteer moderator Volunteer tester Project scientist Send message
Joined: 15 Aug 05 Posts: 1957 ID: 352 Credit: 6,139,475,826 RAC: 2,271,747
                                      
|
Am I reading it correctly that sieving up to 1000T will remove about 20% more candidates comparing to sieve up to 1T?
Sieving to 1e15 / 1000T would generate work for ~200 GPUs and a month running 24/7.
2e16 is job for 365 GPUs running 365 days.
This size would need BOINC platform and it's participants.
____________
My stats | |
|
rogueVolunteer developer
 Send message
Joined: 8 Sep 07 Posts: 1256 ID: 12001 Credit: 18,565,548 RAC: 0
 
|
I'm looking into a change for mfsieve/mfsievecl to speed up sieving. It won't double the speed for 1e6 < n < 2e6, but it should be more than 50% faster. It is a matter of computing 1e6! mod p faster than what it does today. | |
|
Post to thread
Message boards :
Sieving :
Automated sieving |