mtsieve - Page 12

ATH · 2019-03-11, 17:44

I found a bug in twinsieve, or at least an unspecified limitation. What is the maximum array of k's it should be able to handle? Right now it is 2^32.

I tried with 50B which takes up 6.2 GB RAM:

twinsieve.exe -b 2 -n 333333 -k 1 -K 5e10 -P 1e9

Code:

2019-03-11 13:17:56: Sieve started: 1 < p < 1e9 with 50000000000 terms (1 < k < 50000000000, k*2^333333) (expecting 50000000000 factors)
2019-03-11 15:14:39: Sieve completed at p=1000000007.  Primes tested 50847534.  Found 49903073399 factors.  96926601 terms remaining.  Time 6937.09 seconds

This first command works fine and it saves the file "k_b2_n333333.pfgw" at P=1e9.

But if you resume the sieve from that file to any higher range, the 2nd time it saves this happens:

twinsieve.exe -i k_b2_n333333.pfgw -P 2e9

Code:

2019-03-11 15:49:17: Sieve started: 1000000007 < p < 2e9 with 96926601 terms (375 < k < 49999999854, k*2^333333) (expecting 3137052 factors

Fatal Error: Something is wrong. Counted terms (90205758) != expected terms (90792073)

The file saved after this bug is now corrupted and if you restart it, this is in the log file:

Code:

2019-03-11 18:31:00: Sieve started: 2000000011 < p < 3e9 with 90205758 terms (375 < k < 4294967654], k*2^333333) (expecting 1676083 factors)

So it is a 32 bit variable issue somewhere. It also tried another exponent and other values of the 1st and 2nd Pmax like 1e11 and 2e11 or 1e12 and 2e12. In the last case the 2nd run is so long that it fails during the run instead of at the end when saving the file again.

rogue · 2019-03-11, 17:54

I don't see anything obviously wrong in the code. I'll have to debug this.

ATH · 2019-03-11, 18:59

Here is a file before the bug happens if that helps:
k_b2_n333333.zip (86 MB, 326 MB unpacked, use 7-zip)

It is run with:
twinsieve.exe -b 2 -n 333333 -K 5e10 -P 1e11

so if you do:

twinsieve.exe -i k_b2_n333333.pfgw -P 11e10

the bug happens in ~2 min on 1 core.

rogue · 2019-03-11, 20:19

Found it. In ProcessInputTermsFile, bit is defined as uint32_t. It should be uint64_t. This bug only affects sieving where k > 2^32 and will fail when writing the output file.

Thomas11 · 2019-05-20, 09:40

I did a quick comparison between twinsieve 1.0.3 and newpgen and noticed that under certain conditions (e.g. pmax > kmin*b^n) twinsieve seems to miss some factors.

For example:
./twinsieve -b 6 -n 1 -k 1 -K 200000000 -f N

returns 4037923 candidates starting with:

Code:

34649:T:0:6:3
1 1
2 1
3 1
5 1
6 1
7 1
...

while
./newpgen -v -t=2 -base=6 -n=1 -kmin=1 -kmax=200000000 -wp=6k.txt

yields 4033838 candidates starting with:

Code:

34666:T:1:6:3
1 1
2 1
3 1
4 1
5 1
7 1
...

Obviously, 6*6^1-1 = 35 has been correctly eliminated by newpgen but missed by twinsieve.

For larger k (e.g. when pmax < k*b^n) twinsieve and newpgen yield identical results...

rogue · 2019-05-21, 01:50

I see what is happening, but fixing it will be more challenging. This issue is more likely to occur with small n and small k, but can happen with larger n and larger k.

rogue · 2019-05-21, 19:19

I have a fix for this. It means that twinsieve will be slightly slower when kmax > p, but should be slightly faster than kmax < p. How deeply one sieves determines how much speed one gains or loses, ut it most likely won't be noticeable.

It appears the newpgen output is also wrong in this case because 4*6+1 is divisible by 5 (so 4 shouldn't be in the output) and both 1*6-1 and 1*6-1 are both prime (so 1 should be in the output). The updated twinsieve correctly leaves 1 and removes 4 from the output.

fbncsieve has the same problem as twinsieve.

newpgen also has the same problem with other fixed k sieves.

This issue can only occur if kmin*b^n < pmax.

pepi37 · 2019-05-21, 20:17

Quote:

Originally Posted by rogue

I have a fix for this. It means that twinsieve will be slightly slower when kmax > p, but should be slightly faster than kmax < p. How deeply one sieves determines how much speed one gains or loses, ut it most likely won't be noticeable.

It appears the newpgen output is also wrong in this case because 4*6+1 is divisible by 5 (so 4 shouldn't be in the output) and both 1*6-1 and 1*6-1 are both prime (so 1 should be in the output). The updated twinsieve correctly leaves 1 and removes 4 from the output.

fbncsieve has the same problem as twinsieve.

newpgen also has the same problem with other fixed k sieves.

This issue can only occur if kmin*b^n < pmax.

Is new twinsieve and fbncsieve online ?

rogue · 2019-05-21, 21:29

Quote:

Originally Posted by pepi37

Is new twinsieve and fbncsieve online ?

It is posted now. You can d/l from this page.

This is version 1.9.0 as there are many changes to support srsieve2, which isn't ready yet. Here are the details:

Code:

   Changes were made to the framework to support srsieve2 (which isn't ready yet).  No other
   sieves use thse features (yet).
   Modify FactorApp in an effort to more accurately compute the factor rate.  When starting
   a new sieve, the factor rate would be inflated because it would calculate the rate based 
   upon all factors removed.  This change will exclude factors removed in the the first 30
   minutes that the program has run.  This logic will be executed when fewer than 60 terms
   have been removed in the previous hour.
   Fixed an issue in fbncsieve and twinsieve where the output file would contain composites
   that are divisible by p that had already been sieved.

pepi37 · 2019-05-21, 21:54

Quote:

Originally Posted by rogue

It is posted now. You can d/l from this page.

This is version 1.9.0 as there are many changes to support srsieve2, which isn't ready yet. Here are the details:

Code:

   Changes were made to the framework to support srsieve2 (which isn't ready yet).  No other
   sieves use thse features (yet).
   Modify FactorApp in an effort to more accurately compute the factor rate.  When starting
   a new sieve, the factor rate would be inflated because it would calculate the rate based 
   upon all factors removed.  This change will exclude factors removed in the the first 30
   minutes that the program has run.  This logic will be executed when fewer than 60 terms
   have been removed in the previous hour.
   Fixed an issue in fbncsieve and twinsieve where the output file would contain composites
   that are divisible by p that had already been sieved.

Link is old

http://www.mersenneforum.org/rogue/mtsieve_1.8.4.7z

rogue · 2019-05-22, 02:10

Quote:

Originally Posted by pepi37

Link is old

http://www.mersenneforum.org/rogue/mtsieve_1.8.4.7z

Are you sure? I see 1.9.0

2019-03-11, 17:44	#122
ATH Einyen Dec 2003 Denmark 2²×863 Posts	I found a bug in twinsieve, or at least an unspecified limitation. What is the maximum array of k's it should be able to handle? Right now it is 2^32. I tried with 50B which takes up 6.2 GB RAM: twinsieve.exe -b 2 -n 333333 -k 1 -K 5e10 -P 1e9 Code: 2019-03-11 13:17:56: Sieve started: 1 < p < 1e9 with 50000000000 terms (1 < k < 50000000000, k2^333333) (expecting 50000000000 factors) 2019-03-11 15:14:39: Sieve completed at p=1000000007. Primes tested 50847534. Found 49903073399 factors. 96926601 terms remaining. Time 6937.09 seconds This first command works fine and it saves the file "k_b2_n333333.pfgw" at P=1e9. But if you resume the sieve from that file to any higher range, the 2nd time it saves this happens: twinsieve.exe -i k_b2_n333333.pfgw -P 2e9* Code: 2019-03-11 15:49:17: Sieve started: 1000000007 < p < 2e9 with 96926601 terms (375 < k < 49999999854, k2^333333) (expecting 3137052 factors Fatal Error: Something is wrong. Counted terms (90205758) != expected terms (90792073)* The file saved after this bug is now corrupted and if you restart it, this is in the log file: Code: 2019-03-11 18:31:00: Sieve started: 2000000011 < p < 3e9 with 90205758 terms (375 < k < 4294967654], k2^333333) (expecting 1676083 factors) So it is a 32 bit variable issue somewhere. It also tried another exponent and other values of the 1st and 2nd Pmax like 1e11 and 2e11 or 1e12 and 2e12. In the last case the 2nd run is so long that it fails during the run instead of at the end when saving the file again. Last fiddled with by ATH on 2019-03-11 at 17:45*

2019-05-20, 09:40	#126
Thomas11 Feb 2003 2⁷·3·5 Posts	I did a quick comparison between twinsieve 1.0.3 and newpgen and noticed that under certain conditions (e.g. pmax > kminb^n) twinsieve seems to miss some factors. For example: ./twinsieve -b 6 -n 1 -k 1 -K 200000000 -f N* returns 4037923 candidates starting with: Code: 34649:T:0:6:3 1 1 2 1 3 1 5 1 6 1 7 1 ... while ./newpgen -v -t=2 -base=6 -n=1 -kmin=1 -kmax=200000000 -wp=6k.txt yields 4033838 candidates starting with: Code: 34666:T:1:6:3 1 1 2 1 3 1 4 1 5 1 7 1 ... Obviously, 66^1-1 = 35 has been correctly eliminated by newpgen but missed by twinsieve. For larger k (e.g. when pmax < kb^n) twinsieve and newpgen yield identical results...

2019-03-11, 17:54	#123
rogue "Mark" Apr 2003 Between here and the 7341₁₀ Posts	I don't see anything obviously wrong in the code. I'll have to debug this.

2019-03-11, 18:59	#124
ATH Einyen Dec 2003 Denmark D7C₁₆ Posts	Here is a file before the bug happens if that helps: k_b2_n333333.zip (86 MB, 326 MB unpacked, use 7-zip) It is run with: twinsieve.exe -b 2 -n 333333 -K 5e10 -P 1e11 so if you do: twinsieve.exe -i k_b2_n333333.pfgw -P 11e10 the bug happens in ~2 min on 1 core.

2019-03-11, 20:19	#125
rogue "Mark" Apr 2003 Between here and the 1110010101101₂ Posts	Found it. In ProcessInputTermsFile, bit is defined as uint32_t. It should be uint64_t. This bug only affects sieving where k > 2^32 and will fail when writing the output file.

2019-05-21, 01:50	#127
rogue "Mark" Apr 2003 Between here and the 3·2,447 Posts	I see what is happening, but fixing it will be more challenging. This issue is more likely to occur with small n and small k, but can happen with larger n and larger k.

2019-05-21, 19:19	#128
rogue "Mark" Apr 2003 Between here and the 3×2,447 Posts	I have a fix for this. It means that twinsieve will be slightly slower when kmax > p, but should be slightly faster than kmax < p. How deeply one sieves determines how much speed one gains or loses, ut it most likely won't be noticeable. It appears the newpgen output is also wrong in this case because 46+1 is divisible by 5 (so 4 shouldn't be in the output) and both 16-1 and 16-1 are both prime (so 1 should be in the output). The updated twinsieve correctly leaves 1 and removes 4 from the output. fbncsieve has the same problem as twinsieve. newpgen also has the same problem with other fixed k sieves. This issue can only occur if kminb^n < pmax.