mtsieve - Page 7

rogue · 2018-07-26, 21:43

I've posted 1.7.1 which fixes that bug and a couple in psieve.

rogue · 2018-08-04, 15:43

I have posted 1.7.3 of the framework (1.7.2 was not posted). It fixes the following issues:

Code:

   Fixed a memory exception that would crash any GPU workers immediately.
   Do not output factor rate if no factors found.
   Fixed another issue in non-AVX psieve code that causes it to crash.
   Fixed issue with reading ABCD files as input lines with 1 character would be skipped.
   Fixed a crash upon exit of fbncsieve.
   Allow override with -p when starting fbncsieve and fkbnsieve from an input file.

rogue · 2018-08-04, 16:02

If using gfndsieve, fkbnsieve, or fbncsieve, you should play around with larger values for the -w switch. Each inner loop has a single powmod followed by either addition or bit shifting. This means that each range of p is processed super quick. I have found that gfndsieve has a 20% performance boost by switching to -w7 (-w6 is the default), which means that each worker will process a chunk of 1e7 primes before getting the next chunk of primes. Eventually these sieves will get AVX support, but the framework doesn't have all of the routines I would need to do that. I do not know the speed-up that it will give, but I would hope that it is around 20%.

Sieves such as mfsieve, afsieve, and psieve are much slower as they have a mulmod for each term. For those sieves the default setting for -w is 1e5 or lower as the typical sieve has many thousands of terms.

I haven't done a lot of testing with the other sieves to determine the optimal setting for -w, but it will likely be highly dependent upon how many terms are in the range you are testing. I recommend testing to p=1e6 with the default setting for -w, then testing with different values of -w in ranges above that to see where you get the most bang for the buck. I would like to know what you discover when you do that.

ET_ · 2018-08-04, 16:45

Quote:

Originally Posted by rogue

I have posted 1.7.3 of the framework (1.7.2 was not posted). It fixes the following issues:

Code:

   Fixed a memory exception that would crash any GPU workers immediately.
   Do not output factor rate if no factors found.
   Fixed another issue in non-AVX psieve code that causes it to crash.
   Fixed issue with reading ABCD files as input lines with 1 character would be skipped.
   Fixed a crash upon exit of fbncsieve.
   Allow override with -p when starting fbncsieve and fkbnsieve from an input file.

I experimented a (constant) crash upon exiting gfndsieve. Or better, a core dump. I assume it's a problem involving reading past EOF. Maybe mtsieve version 1.7.3 will correct it as well. (YES, it works fine now)

ET_ · 2018-08-04, 17:36

Quote:

Originally Posted by rogue

If using gfndsieve, fkbnsieve, or fbncsieve, you should play around with larger values for the -w switch. Each inner loop has a single powmod followed by either addition or bit shifting. This means that each range of p is processed super quick. I have found that gfndsieve has a 20% performance boost by switching to -w7 (-w6 is the default), which means that each worker will process a chunk of 1e7 primes before getting the next chunk of primes. Eventually these sieves will get AVX support, but the framework doesn't have all of the routines I would need to do that. I do not know the speed-up that it will give, but I would hope that it is around 20%.

Sieves such as mfsieve, afsieve, and psieve are much slower as they have a mulmod for each term. For those sieves the default setting for -w is 1e5 or lower as the typical sieve has many thousands of terms.

I haven't done a lot of testing with the other sieves to determine the optimal setting for -w, but it will likely be highly dependent upon how many terms are in the range you are testing. I recommend testing to p=1e6 with the default setting for -w, then testing with different values of -w in ranges above that to see where you get the most bang for the buck. I would like to know what you discover when you do that.

Tried the -w switch with 1e7 but in a somewhat different environment:

4GB of RAM - 2 threads - 3.0 GHz - Intel G2030
In parallel with 2 threads already running other computationally-heavy programs.

Results:

Code:

./gfndsieve -k 1200 -K 10000 -P 100000000000000 -n 30000 -N39999 
gfndsieve v1.4, a program to find factors of k*2^n+1 numbers for variable k and n
Sieve started: k*2^n+1, 1201 < k < 9999, 30000 <= n <= 39999, 3 <= p < 1e14 with 44000000 terms
^Cp=256203221, 65.57K p/sec, 41448643 factors found at 786.9 f/sec, 0.0% done. ETC 2021-08-11 02:00            
CTRL-C accepted.  Please wait for threads to completed.

Sieve interrupted at p=275604547.
Processor time: 135.78 sec. (0.09 sieving) (0.54 cores)
2545082 terms written to gfnd.pfgw
Primes tested: 15000000.  Factors found: 41454918.  Remaining terms: 2545082.  Time: 253.74 seconds.

luigi@luigi-Aspire-MC605:~/luigi/mtsieve_1.7.3$ ./gfndsieve -k 1200 -K 10000 -P 100000000000000 -n 30000 -N39999 -w 1e7
gfndsieve v1.4, a program to find factors of k*2^n+1 numbers for variable k and n
Sieve started: k*2^n+1, 1201 < k < 9999, 30000 <= n <= 39999, 3 <= p < 1e14 with 44000000 terms
^Cp=179424691, 0.000 p/sec, 41474702 factors found at 541.5 f/sec, 0.0% done. ETC 2024-01-19 00:28             
CTRL-C accepted.  Please wait for threads to completed.

Sieve interrupted at p=373587911.
Processor time: 178.15 sec. (0.17 sieving) (0.51 cores)
2505902 terms written to gfnd.pfgw
Primes tested: 20000000.  Factors found: 41494098.  Remaining terms: 2505902.  Time: 348.17 seconds.

Let me know if you want me to try with other parameters

Dylan14 · 2018-08-07, 14:37

I have updated the webpage for mtsieve to include documentation for gcwsieve and psieve, as well as provide a version history. It is attached below:

Dylan14 · 2018-08-07, 22:35

I found a bug when using the -s flag in xyyxsieve. If -s b is used, the sieve works fine:

Code:

C:\Users\Dylan_000\Desktop\mtsieve\mtsieve>xyyxsieve -W 4 -P 1e9 -x 100e3 -X 100000 -y 2 -Y 100000 -s b
xyyxsieve v1.3, a program to find factors numbers of the form x^y+y^x
Quick elimination of terms info (in order of check):
    100000 because the term is even
    20000 because x and y have a common divisor
Sieve started: 3 < p < 1e9 with 79998 terms
  p=143390813, 133.9K p/sec, 79896 factors found at 329.9 f/sec, 14.3% done. ETC 2018-08-07 18:35
CTRL-C accepted.  Please wait for threads to completed.

Sieve interrupted at p=174025441.
Processor time: 246.58 sec. (0.33 sieving) (3.60 cores)
98 terms written to xyyx.pfgw
Primes tested: 9715520.  Factors found: 79900.  Remaining terms: 98.  Time: 68.54 seconds.

However, if either + or - is used, the program shows that the sieve is starting and then it quits without giving any further output:

Code:

C:\Users\Dylan_000\Desktop\mtsieve\mtsieve>xyyxsieve -W 4 -P 1e9 -x 100e3 -X 100000 -y 2 -Y 100000 -s +
xyyxsieve v1.3, a program to find factors numbers of the form x^y+y^x
Quick elimination of terms info (in order of check):
    50000 because the term is even
    10000 because x and y have a common divisor
Sieve started: 3 < p < 1e9 with 39999 terms

Code:

C:\Users\Dylan_000\Desktop\mtsieve\mtsieve>xyyxsieve -W 4 -P 1e9 -x 100e3 -X 100000 -y 2 -Y 100000 -s -
xyyxsieve v1.3, a program to find factors numbers of the form x^y+y^x
Quick elimination of terms info (in order of check):
    50000 because the term is even
    10000 because x and y have a common divisor
Sieve started: 3 < p < 1e9 with 39999 terms

rogue · 2018-08-11, 01:32

Thanks Dylan. I have updated the page and I found and fixed the bug in xyyxsieve. You can now d/l version 1.7.4 of the framework. Here are the changes:

Code:

   Modify pixsieve to report primes.
   Modify pixsieve to output search string to console and log when sieve starts.
   Fixed a crash in xyyxsieve when sieving only one sign.
   Generate default filename for mfsieve if not specified on the command line.
   Fix issue in psieve if it finds a factor for the last term of the input.
   
   mfsieve supports AVX and is about 40% faster than previously.

ET_ · 2018-08-11, 10:18

Quote:

Originally Posted by rogue

Thanks Dylan. I have updated the page and I found and fixed the bug in xyyxsieve. You can now d/l version 1.7.4 of the framework. Here are the changes:

Code:

   Modify pixsieve to report primes.
   Modify pixsieve to output search string to console and log when sieve starts.
   Fixed a crash in xyyxsieve when sieving only one sign.
   Generate default filename for mfsieve if not specified on the command line.
   Fix issue in psieve if it finds a factor for the last term of the input.
   
   mfsieve supports AVX and is about 40% faster than previously.

Nice job

rogue · 2018-08-14, 21:49

I have posted 1.7.5 of the framework. It fixes the following issues:

Code:

   Fixed a crash when reading multiple empty lines in a row from an input file.
   Added -r option to fbncsieve to remove terms where k % base = 0.
   Various updates for newpgen output from fbncsieve:
       use the .npg extension instead of .pfgw extension
       change third parameter of first line to 1 for srsieve/srfile compatibility
       change last parameter of first line to 1/2 since 1/2 is used for fixed newpgen
       sieves and 257/258 are used for fixed k sieves.

pepi37 · 2018-08-14, 22:23

Quote:

Originally Posted by rogue

I have posted 1.7.5 of the framework. It fixes the following issues:

Code:

   Fixed a crash when reading multiple empty lines in a row from an input file.
   Added -r option to fbncsieve to remove terms where k % base = 0.
   Various updates for newpgen output from fbncsieve:
       use the .npg extension instead of .pfgw extension
       change third parameter of first line to 1 for srsieve/srfile compatibility
       change last parameter of first line to 1/2 since 1/2 is used for fixed newpgen
       sieves and 257/258 are used for fixed k sieves.

Thanks!
Great update!

2018-07-26, 21:43	#67
rogue "Mark" Apr 2003 Between here and the 2⁴·467 Posts	I've posted 1.7.1 which fixes that bug and a couple in psieve.

2018-08-04, 16:02	#69
rogue "Mark" Apr 2003 Between here and the 2⁴·467 Posts	If using gfndsieve, fkbnsieve, or fbncsieve, you should play around with larger values for the -w switch. Each inner loop has a single powmod followed by either addition or bit shifting. This means that each range of p is processed super quick. I have found that gfndsieve has a 20% performance boost by switching to -w7 (-w6 is the default), which means that each worker will process a chunk of 1e7 primes before getting the next chunk of primes. Eventually these sieves will get AVX support, but the framework doesn't have all of the routines I would need to do that. I do not know the speed-up that it will give, but I would hope that it is around 20%. Sieves such as mfsieve, afsieve, and psieve are much slower as they have a mulmod for each term. For those sieves the default setting for -w is 1e5 or lower as the typical sieve has many thousands of terms. I haven't done a lot of testing with the other sieves to determine the optimal setting for -w, but it will likely be highly dependent upon how many terms are in the range you are testing. I recommend testing to p=1e6 with the default setting for -w, then testing with different values of -w in ranges above that to see where you get the most bang for the buck. I would like to know what you discover when you do that.