mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2020-04-22, 12:31   #243
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

10111010000012 Posts
Default

I cannot speak for llr as I do not maintain it.

pfgw is best suited for whatever llr cannot do. It is also best suited to do primality testing on forms that other programs can only do a PRP test on, such as genefer/geneferocl.

The mtsieve framework is here. There are a nearly 20 sieving programs based upon it including srsieve2 (not to be confused with sr2sieve), which you can d/l from the aforementioned link.
rogue is offline   Reply With Quote
Old 2020-04-22, 13:49   #244
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

2·811 Posts
Default

Quote:
Originally Posted by rogue View Post
I cannot speak for llr as I do not maintain it.

pfgw is best suited for whatever llr cannot do. It is also best suited to do primality testing on forms that other programs can only do a PRP test on, such as genefer/geneferocl.

The mtsieve framework is here. There are a nearly 20 sieving programs based upon it including srsieve2 (not to be confused with sr2sieve), which you can d/l from the aforementioned link.
Sophie Germain is one that PFGW does quite well. There are other forms in it's documentation, which I cannot remember.

I found the mfsieve collection late yesterday evening. I was amazed as to how many different programs are in the archive. Without any general description, it is difficult to determine what each does.
storm5510 is offline   Reply With Quote
Old 2020-04-22, 14:36   #245
axn
 
axn's Avatar
 
Jun 2003

10010011100002 Posts
Default

Quote:
Originally Posted by storm5510 View Post
"The mfsieve framework."
Quote:
Originally Posted by storm5510 View Post
You refer to mfsieve as a group of programs.
Quote:
Originally Posted by storm5510 View Post
I found the mfsieve collection late yesterday evening.
mtsieve, not mfsieve.
axn is offline   Reply With Quote
Old 2020-04-22, 14:41   #246
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5,953 Posts
Default

Quote:
Originally Posted by storm5510 View Post
Sophie Germain is one that PFGW does quite well. There are other forms in it's documentation, which I cannot remember.

I found the mtsieve collection late yesterday evening. I was amazed as to how many different programs are in the archive. Without any general description, it is difficult to determine what each does.
Look at the mtsieve thread. Most of the individual programs are detailed here although I know it isn't up to date.

I actually think that writing a sieve for Sophie-Germain primes would be fairly easy as it could use a lot of the same logic in twinsieve. What program do people use for sieving Sophie-Germain primes? I could easily see if building such a sieve in the mtsieve framework has value.
rogue is offline   Reply With Quote
Old 2020-04-22, 17:49   #247
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

7·17·37 Posts
Default

I used a fixed-n sieve in NewPGen. I haven't looked for SG primes in quite a few years, though.
VBCurtis is offline   Reply With Quote
Old 2020-04-22, 18:52   #248
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

10111010000012 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
I used a fixed-n sieve in NewPGen. I haven't looked for SG primes in quite a few years, though.
fbncsieve (in the mtsieve framework) should be much faster than the fixed-n sieve of NewPGen.
rogue is offline   Reply With Quote
Old 2020-04-22, 23:12   #249
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

65616 Posts
Default

Quote:
Originally Posted by axn View Post
mtsieve, not mfsieve.
I stand corrected. I was unable to see the difference.

Quote:
Originally Posted by rogue
Look at the mtsieve thread. Most of the individual programs are detailed here although I know it isn't up to date.
An interesting document. Thank you.
storm5510 is offline   Reply With Quote
Old 2020-04-23, 04:55   #250
Citrix
 
Citrix's Avatar
 
Jun 2003

62716 Posts
Default

Quote:
Originally Posted by Citrix View Post
Srsieve2.exe is extremely slow for low weight numbers. I am trying to modify sr1sieve.exe for these. Looking at the source I only need to modify LIMIT_BASE (-Q flag).

https://www.mersenneforum.org/showpo...&postcount=256
https://www.mersenneforum.org/showth...529034#post256

If Srsieve2.exe could have this then I do not use sr1sieve.exe
I was sieving a range of 10M for my extreme low weight k.
Using a Q value ~ 2500 this can be reduced to a range of around 4096.
I get a speed up of 2.5 times. Much lower than expected.

Looking through the source code of all 3 programs. Some suggestions:-
1. There is too much overhead in all 3 programs. Most of the specializations theoretically should make the program faster but I think they are making it slower. Simplifying the code might make it faster.

2. In Mtsieve there is a function GenericSubsequenceHelper::FindBestQ()
A better Q can be found using gcd. There are simpler ways of finding best Q. The best theoretical Q might not always be the fastest.

3. For the babystep and giantstep code, using a hashmap/bitmap instead of a hashtable can make the program much faster with no significant extra memory use.

4. The program (srsieve2) can be ported to a GPU in most cases (as long as the range is not too large or the weight is extremely low). For low weight sequences a GPU version will be very helpful as they cannot be sieved very far on the CPU.

Let me know if you are interested in implementing any of the above and need help.

Thanks.

Last fiddled with by Citrix on 2020-04-23 at 04:59
Citrix is offline   Reply With Quote
Old 2020-04-23, 12:18   #251
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

135018 Posts
Default

Quote:
Originally Posted by Citrix View Post
I was sieving a range of 10M for my extreme low weight k.
Using a Q value ~ 2500 this can be reduced to a range of around 4096.
I get a speed up of 2.5 times. Much lower than expected.

Looking through the source code of all 3 programs. Some suggestions:-
1. There is too much overhead in all 3 programs. Most of the specializations theoretically should make the program faster but I think they are making it slower. Simplifying the code might make it faster.

2. In Mtsieve there is a function GenericSubsequenceHelper::FindBestQ()
A better Q can be found using gcd. There are simpler ways of finding best Q. The best theoretical Q might not always be the fastest.

3. For the babystep and giantstep code, using a hashmap/bitmap instead of a hashtable can make the program much faster with no significant extra memory use.

4. The program (srsieve2) can be ported to a GPU in most cases (as long as the range is not too large or the weight is extremely low). For low weight sequences a GPU version will be very helpful as they cannot be sieved very far on the CPU.

Let me know if you are interested in implementing any of the above and need help.
I appreciate your feedback.

As for #1, I'm not certain if you are referring to srsieve2 or srsieve/sr1sieve/sr2sieve. If srsieve2, I'm open to suggestions. Note that I aim for easy of development/support over speed. Sacrificing up to 1 percent to achieve that is acceptable because I can typically make up for it in other areas. Also for srsieve2, it is still a work in progress. You have probably noticed that it is designed to switch the helper/worker if certain conditions are met as each helper/worker will have very different logic meant to optimize in certain ways.

As for #3, I did try to implement a hashmap, but the performance was worse. I didn't dig into determining why as the implementation I had was supposed to be one of the fastest.

As for #4, it is on my radar, but I haven't don anything yet. My focus has been on implementing the Legendre tables that sr1sieve and sr2sieve have, but bsgs code using those tables a hornet's nest.

I'm open to any suggestions. If you want to play around with the code and try your hand at some optimizations, I'm all for it.

To continue this, we can either move this discussion to the mtsieve thread, to a new thread, or take offline via PM or e-mail. If we keep it online then other participants of this forum can add their knowledge to the discussion or can learn from it.
rogue is offline   Reply With Quote
Old 2020-04-23, 14:12   #252
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×47×61 Posts
Default

Quote:
Originally Posted by rogue View Post
If we keep it online then other participants of this forum can add their knowledge to the discussion or can learn from it.
And enjoy reading it
henryzz is offline   Reply With Quote
Old 2020-04-23, 15:17   #253
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5,953 Posts
Default

I created this thread for mtsieve improvemets.
rogue is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving twins with srsieve henryzz Twin Prime Search 0 2014-03-18 12:44
Intel announces multi-core enhancements for Haswell chips ixfd64 Hardware 8 2012-02-10 20:32
LLRnet enhancements kar_bon No Prime Left Behind 10 2008-03-28 11:21
TODO list and suggestions/comments/enhancements Greenbank Octoproth Search 2 2006-12-03 17:28
Suggestions for future enhancements Reboot It Software 16 2003-10-17 01:31

All times are UTC. The time now is 23:07.

Thu Oct 29 23:07:01 UTC 2020 up 49 days, 20:17, 1 user, load averages: 2.41, 2.36, 2.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.