Software/instructions/questions

[gd_barnes]

I got it running and completed phase 1 to n=100 for S586 k=6000001 to 7000000. I'm only using that as a starting test to see if my setup works. I'll be running lots of bases and ranges for detailed testing.

I didn't know that there was more than one version of srsieve2 1.7 floating around. Clearly I got the correct one this time. :-)

For some reason, I thought it was multi-core. But that's no problem. Just like the starting bases script, I'll run as many instances as I have cores.

I like the color highlight from the most recent update of srbsieve.

I'll be doing a lot of parallel testing with the starting bases script including for huge k's > 1e10. They can actually test each other there.

[gd_barnes]

Mark, please don't do official testing of S586 with the new srbsieve process until it has been extensively parallel tested.

Two problems that I've noticed, one minor and one major, in running the parallel test against the starting bases script for S586 k=6000001 to 7000000:

1. It is skipping k=7000000. It's not in any file. When I add up the k's in all of the files, there are 999999 terms. In srbsieve.ini, I have mink=6000001 and maxk=7000000. There should be 1000000 total terms inclusive.

2. It is missing many primes for n=1 to 5 in in the initial phase that runs fbncsieve. (I have maxNfbncsieve=5 in the ini file.) This is causing it to find larger primes for the same k or for the k to end up in the remaining file when it should not be. I have attached all of the primes that it is missing.

As a point of reference, there should be 51497 k's remaining for S586 k=6000001-7000000 at n=100. Srbsieve shows 51513 k's remaining. The small 16 k difference is as a result of it finding larger primes for the k's where small primes were missed.

I hope the previous version of srbsieve that used NewPGen was not missing small primes in this manner.

The good news is that srbsieve ran the above range in 33 minutes on one core with nothing else running in the background. The starting bases script took 66 minutes. No surprise with using more modern software.

[rogue]

Originally Posted by gd_barnes

Mark, please don't do official testing of S586 with the new srbsieve process until it has been extensively parallel tested.

Two problems that I've noticed, one minor and one major, in running the parallel test against the starting bases script for S586 k=6000001 to 7000000:

1. It is skipping k=7000000. It's not in any file. When I add up the k's in all of the files, there are 999999 terms. In srbsieve.ini, I have mink=6000001 and maxk=7000000. There should be 1000000 total terms inclusive.

2. It is missing many primes for n=1 to 5 in in the initial phase that runs fbncsieve. (I have maxNfbncsieve=5 in the ini file.) This is causing it to find larger primes for the same k or for the k to end up in the remaining file when it should not be. I have attached all of the primes that it is missing.

I hope the previous version of srbsieve that used NewPGen was not missing primes in this manner.

Okay. That would be a problem with fbncsieve, which I will look into. I will look at the missing value at the high end of the range.

[gd_barnes]

Originally Posted by rogue

Okay. That would be a problem with fbncsieve, which I will look into. I will look at the missing value at the high end of the range.

OK thanks. I edited that post before you responded to include a little more info.

[gd_barnes]

Observation: When PFGW runs in the various phases of srbsieve, I see that it loops through all of the k's and runs a PRP test (no primality proof) on everything. When it is done looping through all k's, it then runs a primality proof on all of the PRP's. Seems reasonable enough.

What does it do if a PRP turns out to be composite?

If a PRP is composite, it should continue searching that k through the rest of the sieve file. But it appears to not be in that step of the process at that point. Is there special code in place to cause it to "back track" to continue searching only that k?

Composite PRPs would happen relatively often in phase 1, albeit almost never in subsequent phases. I've never seen the starting bases script write out a composite PRP for n > ~25. (It does write them in a separate file, mostly for informational and entertainment purposes. They serve no actual purpose in the conjecture.)

Like srbsieve, the starting bases script initially does PRP tests because they are faster. But it is still in the k looping process at that point. So if it finds a PRP, it immediately does a proof at that point. If it turns out composite, then it continues on searching that k in the normal k looping process.

[kar_bon]

Originally Posted by gd_barnes

2. It is missing many primes for n=1 to 5 in in the initial phase that runs fbncsieve. (I have maxNfbncsieve=5 in the ini file.) This is causing it to find larger primes for the same k or for the k to end up in the remaining file when it should not be. I have attached all of the primes that it is missing.

It's the same behaviour as in other sieving programs like gcwsieve.

Sieving the n-range 2-10000 (n=1 not possible, why?) and a max P of 1e9 for any base it 'misses' mostly primes for n=1 or 2.

Example for gcwsieve Woodall base 7230
The factors files contains the entry
104545799 | 2*7230^2-1
which are the same: the factor found _is_ the number so n=2 is eliminated from the possible prime candidates.
I had to check such small n-values with pfgw and a normal script like

ABC2 $a*$b^$a-1
a: from 1 to 20
b: from 2 to 10000

for small n-values.
Depending on the P-range will miss higher n-values n>2.

I think this is the problem with other sieves, too.

[KEP]

Originally Posted by VBCurtis

When I did R3 work using srbsieve, I found that you had 3 times as many phases as were optimal. I used roughly a tripling of n-range for each phase, and the program ran almost twice as fast to complete a range to n = 5000.

While cutting off phases at FFT cutoffs makes sense, you need more than one FFT length in each phase else you're wasting the sieve. Going from 150 to 200 is just silly; go from 150 to something in 400-600. That's what Rogue is doing, and it's faster by a lot. Try it.

I no longer has my original base 3 srbsieve.ini file, but I do remember that I cleaned up the suggestions Mark had in the phases, because there were too many phases and as you notice I saw an increase. Going too many n's especially in the small n range, is due to the high removal rate actually counterproductive. As FFT growths and n growths it's not unlikely that covering multiple FFTs will speed up the process, wich just confirms, that initially the srbsieve.ini files is just a good suggestion but one has to tweak the numbers themself to see what works best on their system.

Originally Posted by rogue

If the phases are too small, then you are just wasting time sieving and will end up doing more PRP tests. The phases I proposed will allow for deeper sieving, and thus less PRP testing.

Note that -F is specific to the CPU you are running on..

I did not remember or know that of the -F flag.

You do waste ressources, IF you do not reduce or increase the sievevalue accordingly. If not clear, the sievevalue was based on a fixed initial sieve wich gave me an indication of candidates remaining and the amount of k's if I remember correctly was determined by low b/max b and that gave a value that ended up determining the k's to sieve and that amount of k's was part of the formula that determined the sievevalue, so I believe that everything was at least for my system as optimal as possible to be

Originally Posted by kar_bon

It's the same behaviour as in other sieving programs like gcwsieve.

Sieving the n-range 2-10000 (n=1 not possible, why?) and a max P of 1e9 for any base it 'misses' mostly primes for n=1 or 2.

I think this is the problem with other sieves, too.

And the fact that n=1 can not be sieved is also the reason that I use good old NewPGen. NewPGen is not as fast, but NewPGen is reliable and has been around for many years and NewPGen does not sieve k=1 but it does sieve n=1 as desired and expected.

[gd_barnes]

Mark,

I just found the issue on both problems mentioned yesterday. Neither are a problem with fbncsieve. Both are a problem with the command that is sent by srbsieve to fbncsieve. Here is the command for n=1:

fbncsieve -r -fD -k6000001 -K6999999 -sk*586^^1+1 -o n1.abcd

Fixes:

1. For the missing k=7000000 issue, change the max k switch so that it is equal to the maxk in srbsieve.ini, i.e. -K7000000.

2. For the missing primes issue, remove the -r switch.

The problem was not an error in the sieving process. The -r switch removes k's that are a multiple of the base...not something that we want to do here.

I checked the file of 114 primes that I had posted earlier that it had missed. The k was divisible by 586 in all of them.

I then ran fbncsieve stand-alone using the exact command that srbsieve passes to it but removing the -r switch. Spot checking found that it was finding the primes that were previously missed.

Assuming that fixes both issues, what remains now is the question about how srbsieve handles composite PRP's.

Gary

[rogue]

Originally Posted by gd_barnes

Mark,

I just found the issue on both problems mentioned yesterday. Neither are a problem with fbncsieve. Both are a problem with the command that is sent by srbsieve to fbncsieve. Here is the command for n=1:

fbncsieve -r -fD -k6000001 -K6999999 -sk*586^^1+1 -o n1.abcd

Fixes:

1. For the missing k=7000000 issue, change the max k switch so that it is equal to the maxk in srbsieve.ini, i.e. -K7000000.

2. For the missing primes issue, remove the -r switch.

The problem was not an error in the sieving process. The -r switch removes k's that are a multiple of the base...not something that we want to do here.

I checked the file of 114 primes that I had posted earlier that it had missed. The k was divisible by 586 in all of them.

I then ran fbncsieve stand-alone using the exact command that srbsieve passes to it but removing the -r switch. Spot checking found that it was finding the primes that were previously missed.

Assuming that fixes both issues, what remains now is the question about how srbsieve handles composite PRP's.

Thanks Gary. That will save me a lot of time.

I was under the assumption that composite PRPs don't happen. If they do they are extremely rare, but they could still happen.

I could switch to LLR which combines the PRP and primality tests. I don't want to do that with pfgw. The alternative is to write the PRPs that are composite to another file and do a post processing for the phase that re-runs them.

The bug with k=7000000 is also in fbncsieve. The code is to remove even k, but only when the base = 2. It was removing even k when the base is even. I will restart the range after I make this fix. Fortunately it hasn't cost me much time. I wanted to make a change to how I ran the range anyways.

Does anyone here have an opinion on how to handle PRPs that are actually composite? IIRC llr is slower than pfgw with small n.

[storm5510]

@rogue

Success!

I stopped it after running 12+ hours. A small checkpoint file indicated it was on phase 400 to 649 of the group you posted previously. Perhaps my choice of a test candidate was not the best. I was able to glean a bit of information by looking at the various smaller files with Notepad++. There were many leftovers to choose from.

Based on what I read just above, there are other items which need attention so I will just sit back and watch. I doubt I would ever do anything useful lest I get pounded on the head with a mallet by Gary. This is his show and I would not want to add to his burden. Besides, I have two sieves running for him on front burners now. I may experiment a bit more though.

Thank you for your patience!

[gd_barnes]

Originally Posted by rogue

Thanks Gary. That will save me a lot of time.

I was under the assumption that composite PRPs don't happen. If they do they are extremely rare, but they could still happen.

I could switch to LLR which combines the PRP and primality tests. I don't want to do that with pfgw. The alternative is to write the PRPs that are composite to another file and do a post processing for the phase that re-runs them.

The bug with k=7000000 is also in fbncsieve. The code is to remove even k, but only when the base = 2. It was removing even k when the base is even. I will restart the range after I make this fix. Fortunately it hasn't cost me much time. I wanted to make a change to how I ran the range anyways.

Does anyone here have an opinion on how to handle PRPs that are actually composite? IIRC llr is slower than pfgw with small n.

Composite PRPs definitely happen! I've seen many while using the starting bases script because it writes them to a separate file for info purposes only. They occur at very small n-values, typically in the n=~5 to 20 range. But as we have found it is at the smallest of n-values where the biggest problems lie when it comes to software running the conjectures.

The process as currently coded is logically incorrect. You have a lot of PRPs. 1 out of 5-10 million of them may be composite. If it is, it must be thrown out and the k needs to continue being searched.

I'm now wondering how the previous srbsieve was coded. Hmmm.....

Option 1 is to prove the PRP as prime right after the PRP is found similar to what the starting bases script does.

Option 2 as you stated is to write the k and n-value of the composite PRP to a separate file during the global proving process. At the end of that process, then using the original sieve file, continue testing the k at one greater than the n-value that had the composite. At that point in the process, my suggestion would be to do all primality tests (vs. PRP tests) even though it takes a little longer so that you don't have to possibly back track again since the number of tests would be very small in the grand scheme of things.

Based on how things are coded now and the fact that it would be difficult to force PFGW to change, mid-stream, from a PRP to a primality test, I like option 2.

Please don't officially start S586 until fixes are extensively tested. That is what caused us a myriad of problems in the past with sieving software. There are many more exception situations like this that I can come up with. I'm imagining very large k's, k's with algebraic factors that eliminate them from consideration, strange outages in the middle of steps of the process. That's just spitballing for a few seconds. I'm sure there are many more.