srsieve/sr2sieve enhancements

[rogue]

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.

[storm5510]

Originally Posted by rogue

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.

[axn]

Originally Posted by storm5510

"The mfsieve framework."

Originally Posted by storm5510

You refer to mfsieve as a group of programs.

Originally Posted by storm5510

I found the mfsieve collection late yesterday evening.

mtsieve, not mfsieve.

[rogue]

Originally Posted by storm5510

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.

[VBCurtis]

I used a fixed-n sieve in NewPGen. I haven't looked for SG primes in quite a few years, though.

[rogue]

Originally Posted by VBCurtis

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.

[storm5510]

Originally Posted by axn

mtsieve, not mfsieve.

I stand corrected. I was unable to see the difference.

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.

[Citrix]

Originally Posted by Citrix

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.

[rogue]

Originally Posted by Citrix

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.

[henryzz]

Originally Posted by rogue

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

[rogue]

I created this thread for mtsieve improvemets.