It looks like I found another bug in pixsieve. It seems to stop shortly after p=24068943967, which is well short of 2^52:


[CODE]C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>pixsieve -W 12 -w 10000 -P29e9 -i e_100k-1M_primecan.txt -o e_100k-1M_primecan.txt
pixsieve v2.5, a program to find factors of substrings of a decimal string
Sieve started: 24000000131 < p < 29e9 with 21189 terms (100015 <= length <= 999966) (expecting 166 factors)
p=24068943967, 3.942K p/sec, 0 factors found, 1.4% done. ETC 2018-09-29 22:24
C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>[/CODE]
This behavior persists regardless of whether I use the GPU or not:


[CODE]C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>pixsieve -G 1 -D 1 -P29e9 -i e_100k-1M_primecan.txt -o e_100k-1M_primecan.txt
pixsieve v2.5, a program to find factors of substrings of a decimal string
GPU primes per worker is 61440
Sieve started: 24000000131 < p < 29e9 with 21189 terms (100015 <= length <= 999966) (expecting 166 factors)
p=24067958093, 8.058K p/sec, 0 factors found, 1.4% done. ETC 2018-09-29 12:51
C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>[/CODE]

[QUOTE=Dylan14;497056]It looks like I found another bug in pixsieve. It seems to stop shortly after p=24068943967, which is well short of 2^52:


[CODE]C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>pixsieve -W 12 -w 10000 -P29e9 -i e_100k-1M_primecan.txt -o e_100k-1M_primecan.txt
pixsieve v2.5, a program to find factors of substrings of a decimal string
Sieve started: 24000000131 < p < 29e9 with 21189 terms (100015 <= length <= 999966) (expecting 166 factors)
p=24068943967, 3.942K p/sec, 0 factors found, 1.4% done. ETC 2018-09-29 22:24
C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>[/CODE]
This behavior persists regardless of whether I use the GPU or not:


[CODE]C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>pixsieve -G 1 -D 1 -P29e9 -i e_100k-1M_primecan.txt -o e_100k-1M_primecan.txt
pixsieve v2.5, a program to find factors of substrings of a decimal string
GPU primes per worker is 61440
Sieve started: 24000000131 < p < 29e9 with 21189 terms (100015 <= length <= 999966) (expecting 166 factors)
p=24067958093, 8.058K p/sec, 0 factors found, 1.4% done. ETC 2018-09-29 12:51
C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>[/CODE][/QUOTE]

IF this is from the latest release, then I know the problem and it will be fixed. I introduced a bug in mtsieve 1.8.0

[QUOTE=Dylan14;497056]It looks like I found another bug in pixsieve. It seems to stop shortly after p=24068943967, which is well short of 2^52:


[CODE]C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>pixsieve -W 12 -w 10000 -P29e9 -i e_100k-1M_primecan.txt -o e_100k-1M_primecan.txt
pixsieve v2.5, a program to find factors of substrings of a decimal string
Sieve started: 24000000131 < p < 29e9 with 21189 terms (100015 <= length <= 999966) (expecting 166 factors)
p=24068943967, 3.942K p/sec, 0 factors found, 1.4% done. ETC 2018-09-29 22:24
C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>[/CODE]This behavior persists regardless of whether I use the GPU or not:


[CODE]C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>pixsieve -G 1 -D 1 -P29e9 -i e_100k-1M_primecan.txt -o e_100k-1M_primecan.txt
pixsieve v2.5, a program to find factors of substrings of a decimal string
GPU primes per worker is 61440
Sieve started: 24000000131 < p < 29e9 with 21189 terms (100015 <= length <= 999966) (expecting 166 factors)
p=24067958093, 8.058K p/sec, 0 factors found, 1.4% done. ETC 2018-09-29 12:51
C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>[/CODE][/QUOTE]


Does you have speed increase when using GPU?

I have uploaded 1.8.1 which fixes the problem I introduced in 1.8.0.

I modified gfndsieve to use AVX routines, but the performance became much worse so I took that code out.

[QUOTE=pepi37;497171]Does you have speed increase when using GPU?[/QUOTE]

As you can see from the code output, running it on the GPU makes the code run at about 8k primes/sec, whereas the CPU runs it at about 4k primes/sec, so the speed roughly doubles. For reference, the computer I am using to run pixsieve has an Intel Core i7-8750H (6 cores with HT) and a GTX 1050ti.

[QUOTE=rogue;497181]I have uploaded 1.8.1 which fixes the problem I introduced in 1.8.0.

I modified gfndsieve to use AVX routines, but the performance became much worse so I took that code out.[/QUOTE]


-s --independent Sieve +1 and -1 independently - again not working: give empty file as output


[QUOTE]d:\MTSIEVE\TWINSIEVE>twinsieve -P1000000000 -k2 -K1000000 -W4 -b2 -n1778899 -r -fA -s
twinsieve v1.0.0, a program to find factors of k*b^n+1/-1 numbers for fixed b and n and variable k
Fatal Error: Can only support ABC format if sieving +1 and -1 independently[/QUOTE]
I specified ABC file as output

I posted 1.8.2 to fix a crash in twinsieve when using the -s option.

I posed 1.8.3.

I fixed an issue in twinsieve where it couldn't remove factors from an input file.

I added dmdsieve. "dmd" is short for "Double-Mersenne Divisor". It sieves terms of the form 2*k*M+1 where M is a Mersenee Prime. The remaining terms, if prime, are potential divisors of a Double-Mersenne number. This is 2x to 3x faster than mmpsieve. Luigi will be migrating his [URL="http://www.doublemersennes.org/"]project[/URL] to dmdsieve at some point.

[QUOTE=rogue;497629]I posed 1.8.3.

I fixed an issue in twinsieve where it couldn't remove factors from an input file.

I added dmdsieve. "dmd" is short for "Double-Mersenne Divisor". It sieves terms of the form 2*k*M+1 where M is a Mersenee Prime. The remaining terms, if prime, are potential divisors of a Double-Mersenne number. This is 2x to 3x faster than mmpsieve. Luigi will be migrating his [URL="http://www.doublemersennes.org/"]project[/URL] to dmdsieve at some point.[/QUOTE]

I am preparing the download page forr this :smile:
The fact is that my MMpsieve still serves me well on Raspberry PIs.

Thank upu very much for your work, Mark. :bow:

[QUOTE=ET_;497659]I am preparing the download page forr this :smile:
The fact is that my MMpsieve still serves me well on Raspberry PIs.

Thank upu very much for your work, Mark. :bow:[/QUOTE]

If someone can write some ARM assembly, then it could run on those as well.

Mark, need some support to run dmdsieve since nothing happens when I trigger the client with the following flags:


[QUOTE]start /low /min dmdsieve.exe -P 225E12 -i 40_24T.txt -o 40_24T.out -O 40_24T.fact -W 8[/QUOTE] Machine is an ivy bridge, win 7 64 bits.


Even using --help or -h I don't see anything. WIth a DOS windows open nothing happens, with a batch file just vanishes. No crash error...I can't even troubleshoot.
Any dlls I should have on the client folder? (cygwin1.dll, libwinpthread-1.dll, pthreadGC2.dll, pthreadVC2.dll)

[QUOTE=pinhodecarlos;498590]Mark, need some support to run dmdsieve since nothing happens when I trigger the client with the following flags:


Machine is an ivy bridge, win 7 64 bits.


Even using --help or -h I don't see anything. WIth a DOS windows open nothing happens, with a batch file just vanishes. No crash error...I can't even troubleshoot.
Any dlls I should have on the client folder? (cygwin1.dll, libwinpthread-1.dll, pthreadGC2.dll, pthreadVC2.dll)[/QUOTE]

FYI, all mtsieve threads run with idle/low priority so you don't need to do that.

Are you starting with minp from the input file? If not, you probably want to specify on the command line.

Are you starting with a file output from dmdsieve? The reason is that it won't run if you start with an mmpsieve input file.

If you open a cmd prompt and start from there, what does it output? Does it terminate right away with a message?

If still stuck, please send me a link to the input file.

[QUOTE=rogue;498606]FYI, all mtsieve threads run with idle/low priority so you don't need to do that.

Are you starting with minp from the input file? If not, you probably want to specify on the command line.

Are you starting with a file output from dmdsieve? The reason is that it won't run if you start with an mmpsieve input file.

If you open a cmd prompt and start from there, what does it output? Does it terminate right away with a message?

If still stuck, please send me a link to the input file.[/QUOTE]


Clint terminates without a message. Input file attached.


[QUOTE]

C:\DC\dmdsieve>dmdsieve

C:\DC\dmdsieve>dmdsieve --help

C:\DC\dmdsieve>dmdsieve -help

C:\DC\dmdsieve>dmdsieve -h

C:\DC\dmdsieve>

[/QUOTE]

Was just wondering if I need net framework turned on since on this machine almost windows services are off. Tried the xyy siever and had the same behaviour, nothing happens.

[QUOTE=pinhodecarlos;498687]Was just wondering if I need net framework turned on since on this machine almost windows services are off. Tried the xyy siever and had the same behaviour, nothing happens.[/QUOTE]

That is very odd. I build with mingw64 and link libraries as static so you shouldn't need other dlls to run the code. If it needed a dll, it was squawk at you.

Can you install mingw64 on that machine and build?

[QUOTE=rogue;498688]That is very odd. I build with mingw64 and link libraries as static so you shouldn't need other dlls to run the code. If it needed a dll, it was squawk at you.

Can you install mingw64 on that machine and build?[/QUOTE]
I’ll try it this weekend. Thank you.

Using the precompiled "fbncsieve.exe" v1.3.3 from mtsieve 1.8.3:

The line:
fbncsieve.exe -k 1000000001 -K 2000000000 -s "k*20000038^1+1"

fails with:
Fatal Error: 1771575385*20000038^1+1 mod 200000201 = 11167534

It works for other intervals of k.

[QUOTE=ATH;503323]Using the precompiled "fbncsieve.exe" v1.3.3 from mtsieve 1.8.3:

The line:
fbncsieve.exe -k 1000000001 -K 2000000000 -s "k*20000038^1+1"

fails with:
Fatal Error: 1771575385*20000038^1+1 mod 200000201 = 11167534

It works for other intervals of k.[/QUOTE]

The problem is that it should have stopped at 200000190 and 200000201 is greater than that value. I'll have to add a check to handle that. The is that it should stop sieving at about sqrt(1771575385*20000038).

I have posted mtsieve 1.8.4 on the website. It addresses the following items:

[code]
Added the new Mersenne Prime to dmdsieve.
Fixed an issue in twinsieve and fbncsieve where it can exit with an error when
testing primes above sqrt(max term).
Fixed an issue (impacting all sieves) in computing the factor rate. The issue will manifest itself by
outputting a large factor removal rate. It only occurs after running the sieve continuously for 5 days.
[/code]

I realized that I forgot to fix the link on my page. It is fixed now.

I believe there is a bug with fkbnsieve. I issued the following command to a command prompt:


[CODE]fkbnsieve -W 2 -P 1e9 -c 1 -C 1e6 -s "2*11^75000"[/CODE]which should find factors for numbers of the form 2*11^75000+c for c in the set {1,1e6}. The sieve finishes in a few seconds and generates the following sieve file (saved as k2_n11_n75000+c.pfgw):


[CODE]ABCD 2*11^75000$a [41] // Sieved to 1000000009
+10
+50
+10
+14
+54
+60
+12
+54
+4
+68
[and so on...][/CODE]I then put this file as input to pfgw, and I expect that the first number that it should test is 2*11^75000+41. However, instead I get


[CODE]C:\Users\Dylan_000\Desktop\Carol-Kynea\pfgw_win_3.8.3>pfgw64 "k2_b11_n75000+c.pfgw"
PFGW Version 3.8.3.64BIT.20161203.Win_Dev [GWNUM 28.6]

Recognized ABCD Sieve file:
ABCD File
PRP: 2*11^7500041 1/25945879
^C Handler Routine called, shutting down program[/CODE]which is not right. Also it seems like c = 0 is not a valid number for the -c flag, since I get the following message when I replace -c 1 to -c 0 in the first command line:


[CODE]Fatal Error: kmin must be specified[/CODE]
This is on the last version of mtsieve (v1.8.4).

There is just a + missing in the .pfgw file:

ABCD 2*11^75000[COLOR="Red"][SIZE="4"]+[/SIZE][/COLOR]$a [41] // Sieved to 1000000009

[QUOTE=ATH;510524]There is just a + missing in the .pfgw file:

ABCD 2*11^75000[COLOR=Red][SIZE=4]+[/SIZE][/COLOR]$a [41] // Sieved to 1000000009[/QUOTE]


That is the ticket. Also I have the fix: in line 283 of FixedKBNApp.cpp change


[CODE]fprintf(termsFile, "ABCD %" PRIu64"*%u^%u$a [%" PRId64"] // Sieved to %" PRIu64"\n", il_K, ii_Base, ii_N, c, largestPrime);[/CODE]
to


[CODE]fprintf(termsFile, "ABCD %" PRIu64"*%u^%u+$a [%" PRId64"] // Sieved to %" PRIu64"\n", il_K, ii_Base, ii_N, c, largestPrime);[/CODE]
Also, in lines 98, 101 and 104, instead of kmin and kmax, it should be cmin and cmax.

Thanks for the report. I'll fix the code base.

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:

[B]twinsieve.exe -b 2 -n 333333 -k 1 -K 5e10 -P 1e9[/B]

[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[/CODE]

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:

[B]twinsieve.exe -i k_b2_n333333.pfgw -P 2e9[/B]

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

[I][B]Fatal Error: Something is wrong. Counted terms (90205758) != expected terms (90792073)[/B][/I]

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 < [COLOR="Red"]4294967654[/COLOR]], k*2^333333) (expecting 1676083 factors)[/CODE]

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.

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

Here is a file before the bug happens if that helps:
[URL="http://hoegge.dk/mersenne/k_b2_n333333.zip"]k_b2_n333333.zip[/URL] (86 MB, 326 MB unpacked, use 7-zip)

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

so if you do:

[B]twinsieve.exe -i k_b2_n333333.pfgw -P 11e10[/B]

the bug happens in ~2 min on 1 core.

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.

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:
[B]./twinsieve -b 6 -n 1 -k 1 -K 200000000 -f N[/B]

returns 4037923 candidates starting with:
[CODE]34649:T:0:6:3
1 1
2 1
3 1
5 1
[COLOR="Red"]6 1[/COLOR]
7 1
...
[/CODE]

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

yields 4033838 candidates starting with:
[CODE]34666:T:1:6:3
1 1
2 1
3 1
4 1
5 1
7 1
...
[/CODE]

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...

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.

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.

[QUOTE=rogue;517400]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.[/QUOTE]


Is new twinsieve and fbncsieve online ?

[QUOTE=pepi37;517408]Is new twinsieve and fbncsieve online ?[/QUOTE]

It is posted now. You can d/l from [URL="https://mersenneforum.org/rogue/mtsieve.html"]this page.[/URL]

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.
[/code]

[QUOTE=rogue;517414]It is posted now. You can d/l from [URL="https://mersenneforum.org/rogue/mtsieve.html"]this page.[/URL]

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.
[/code][/QUOTE]




Link is old


[url]http://www.mersenneforum.org/rogue/mtsieve_1.8.4.7z[/url]

[QUOTE=pepi37;517418]Link is old


[url]http://www.mersenneforum.org/rogue/mtsieve_1.8.4.7z[/url][/QUOTE]

Are you sure? I see 1.9.0

I have done some very limited tests with srsieve2. Here are some numbers comparing srsieve to srsieve2:

[code]
srsieve -n25000 -N50000 -P1e8 -m1e8 r56.in
srsieve 1.1.4 -- A sieve for integer sequences in n of the form k*b^n+c.
Read 200 sequences from input file `r56.in'.
srsieve started: 25000 <= n <= 50000, 3 <= p <= 100000000
Split 200 base 3 sequences into 1471 base 3^24 subsequences.
Sieving 3 <= p <= 100000000 eliminated 4838822 terms, 161378 remain.
Wrote [COLOR="Red"]161378 [/COLOR] terms for 200 sequences to srsieve format file `srsieve.out'.
srsieve stopped: at p=100000000 because --pmax was reached.
Processor time: [COLOR="red"]555.30 sec[/COLOR][/code]

[code]
srsieve2 -n25000 -N50000 -P1e8 -fA -sr56.in
srsieve2 v2.0.0, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Sieve started: 2 < p < 1e8 with 5000200 terms (25000 < n < 50000, k*3^n+c) (expecting 4812049 factors)
Split 200 base 3 sequences into 1470 base 3^24 sequences.
Sieve completed at p=100000007.
Processor time: 340.83 sec. (0.00 sieving) (1.00 cores)
161378 terms written to b3_n.pfgw
Primes tested: 4761456. Factors found: 4838822. Remaining terms: [COLOR="red"]161378[/COLOR]. Time: [COLOR="red"]341.24 seconds[/COLOR].
[/code]

srsieve2 is nearly 40% faster than srsieve for this range. :w00t:

I do not know why there is a different number of subsequences, but I will look into that. It doesn't seem to be impacting the results.

I have not incorporated the logic from sr1sieve or sr2sieve into it yet. I really want to focus on making sure this code is solid before I start working on that. I will release the code "as is" once I feel confident in what I've written.

I have to run more tests before I release it. To help me in my testing, could people send me (via PM) sequences that they would like me to run my tests with? Whether it is one sequence or a thousand, I don't care. I will limit the upper bound of sieving based upon the sequences. The key to the testing is ti compare the outputs and times between the two programs.

Here is a comparison between sr2sieve and srsieve2:

[code]sr2sieve -p1e7 -P4e7 -q -i sr_3.abcd
sr2sieve 2.0.0 -- A sieve for multiple sequences k*b^n+/-1 or b^n+/-k.
Read 2489826 terms for 1007 sequences from ABCD format file `sr_3.abcd'.
Split 1007 base 3 sequences into 7082 base 3^12 subsequences.
Expecting to find factors for about 197186.63 terms in this range.
sr2sieve 2.0.0 started: 25000 <= n <= 50000, 10000000 <= p <= 40000000
p=35035009, 95979 p/sec, 179938 factors, 83.5% done, 0 sec/factor, ETA 24 May 14:53
sr2sieve 2.0.0 stopped: at p=40000000 because range is complete.
Found factors for [COLOR="red"]197251 [/COLOR]terms in [COLOR="Red"]513.223 [/COLOR]sec. (expected about 197186.63)[/code]

[code]srsieve2 -ib3_n.pfgw -ob3.out -p1e7 -P4e7
srsieve2 v2.0.0, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Split 1007 base 3 sequences into 3028 base 3^4 sequences.
Sieve started: 1e7 < p < 4e7 with 2489826 terms (25000 < n < 50000, k*3^n+c) (expecting 197187 factors)
p=26274431, 4.040K p/sec, 141072 factors found at 435.4 f/sec, 54.2% done. ETC 2019-05-24 15:01
Sieve completed at p=40000003.
Processor time: 441.67 sec. (0.03 sieving) (1.00 cores)
2292575 terms written to b3.out
Primes tested: 1769076. Factors found: [COLOR="red"]197251[/COLOR]. Remaining terms: 2292575. Time: [COLOR="red"]439.72[/COLOR] seconds.[/code]

Note that the above run of sr2sieve is using Legendre tables and srsieve2 does not use Legendre tables. The extra time for sr2sieve is the time needed to build the Legendre tables. The speeds are actually much closer (well under 10%) if one excludes that time. sr2sieve without Legendre tables is much slower than srsieve2. I will need to run more varied ranges to verify that. If that proves to be true, then that limits the code I need to copy from sr2sieve to srsieve2. srsieve2 will automatically build Legendre tables when p > max(k, n, c) (but only if max(k, n, c) < 2^32). I'll add an option to not build them when I get there.

I forgot that I had mixe FPU and SSE code for testing. Switching to SSE only, the numbers look even better:

[CODE]Primes tested: 1769076. Factors found: [COLOR="Red"]197251[/COLOR]. Remaining terms: 2292575. Time: [COLOR="Red"]341.86[/COLOR] seconds.[/CODE]

It is possible that srsieve2 is now faster than sr2sieve even with Legendre symbols. That will verified with more testing.

I built this on Linux, but couldn't figure out how to get it to link with OpenCL, so I ended up settings "ENABLE_GPU=no".

Also had this build error which forced me to remove srsieve2 from the list of programs in the makefile, after which I was able to build:
[code]
make: *** No rule to make target 'srsieve2', needed by 'all'. Stop.
[/code]

Also the "f/sec" or "sec per factor" calculation seems buggy (for psieve at least)

I got this line at one point
[code]p=10519166057, 3.179K p/sec, 140559 factors found at 15.29 sec per factor, 0.0% done. ETC 4219-12-25 02:25[/code]
Then later in the same run:
[code]p=36020724671, 3.132K p/sec, 150902 factors found at 7.623 f/sec, 0.0% done. ETC 3946-08-09 02:00[/code]
Finally after Ctrl-c:
[code]Primes tested: 1552746720. Factors found: 150913. Remaining terms: 191421. Time: 487670.27 seconds.[/code]
So it seems the overall timing should have been 487670.27 / 150913 ~= 3.23 sec per factor

Another note (*emphasis mine)
[quote=https://mersenneforum.org/rogue/mtsieve.html]
This is the sieveing source from primesieve 6.3, a library whose sole purpose is to generate a list of primes as quickly as possible. [b]Per the primsieve license, no changes should be made to this code.[/b]
[/quote]
I found this statement odd and it made me curious enough to look up the license being used by primesieve:
[url]https://github.com/kimwalisch/primesieve/blob/master/COPYING[/url]
It seems to me that modification is 100% ok, as far as licensing is concerned. However that "COPYING" file should probably be included in your "sieve" directory(if not your top level), especially since all the code comments make reference to it as such.

srsieve2 is still a "work in progress". It is not officially released yet.

The calculation of the factoring rate is rather complex. The first few minutes that the sieve is running significantly skew that rate so the code tries to avoid using data from the first few minutes in the calculation. That being written, I'm sure there is more room for improvement. Anyone is welcome to submit suggestions for improvement.

I put a copy of COPYING into the folder with the primesieve code.

Question about using gfndsieve: how do you determine a good pmax -P setting? At what point is it optimal to move over to PFGW?

[QUOTE=hansl;519200]Question about using gfndsieve: how do you determine a good pmax -P setting? At what point is it optimal to move over to PFGW?[/QUOTE]
I think as any other sieve: when removal rate is lower then processed rate from PFGW

[QUOTE=pepi37;519201]I think as any other sieve: when removal rate is lower then processed rate from PFGW[/QUOTE]

Correct. Assuming that the range being sieved has all terms of relatively the same size (within 20% the number of bits), then use pfgw to do a PRP test on one of the terms. You want the factoring rate to be close to that time.

Of course if any of the mtsieve programs is outputting bad factoring rates, that can be a problem.

[QUOTE=hansl;519151]I built this on Linux, but couldn't figure out how to get it to link with OpenCL, so I ended up settings "ENABLE_GPU=no".
[/QUOTE]

Well I feel a little silly to say this, but all I had to do was add "OPENCL_LIBS=-lOpenCL" in the makefile and that got it working. I guess I was previously assuming that the makefile was already set up for this and that I just hadn't installed the correct library/package for it to work.

So I have been testing out GPU capability in gfndsieve, and as was mentioned earlier in the thread by pepi37, it doesn't do much. I have been trying a bunch of different settings combinations to see if any particular setup is more efficient.
Starting at p=3 I don't see any noticeable load, but it does seem to increase with larger p. So trying pmin=2^34 and pmax=2^35 just as a benchmark, I see 60-75% load on my laptop's Quadro M1000M. Not sure if its really doing more work or just dealing with much more overhead in some way. Nothing I did to try tuning -G or -g at this point would max the load though.

Its difficult to measure what optimal settings are, since the CPU throughput dwarfs the GPU, so maybe its a moot point to try tuning at this stage, but would it be possible to support -W0 when -G is nonzero to make GPU-only tuning more testable?

Anyways I don't know a whole lot about optimizing OpenCL or CUDA configurations, but I'm wondering if there's a general rule of thumb for setting -G and -g? Does it make most sense to set -G equal to the number of "Compute Units" aka "Streaming Multiprocessors"? Maybe add 1 or 2 to help keep the work queue filled or does that not help?
Then I guess set -g to whatever still fits comfortably in GPU memory?

Here's a portion of output from "clinfo" for what its worth.
[code]
Device Name Quadro M1000M
Device Vendor NVIDIA Corporation
Device Vendor ID 0x10de
Device Version OpenCL 1.2 CUDA
Driver Version 418.39
Device OpenCL C Version OpenCL C 1.2
Device Type GPU
Device Topology (NV) PCI-E, 01:00.0
Device Profile FULL_PROFILE
Device Available Yes
Compiler Available Yes
Linker Available Yes
Max compute units 4
Max clock frequency 1071MHz
Compute Capability (NV) 5.0
Device Partition (core)
Max number of sub-devices 1
Supported partition types None
Max work item dimensions 3
Max work item sizes 1024x1024x64
Max work group size 1024
Preferred work group size multiple 32
Warp size (NV) 32
Preferred / native vector sizes
char 1 / 1
short 1 / 1
int 1 / 1
long 1 / 1
half 0 / 0 (n/a)
float 1 / 1
double 1 / 1 (cl_khr_fp64)
[/code]
The GPU has 512 total "cuda cores" by the way, since clinfo doesn't seem to provide that number in its output anywhere.

I could allow for -W0, but some sieves have other constraints which require a minimum p before using the GPU.

It is certainly possible that someone could write better OpenCL code than I. Some sieves will see a noticeable gain when using the GPU and others will not.

And I have suggestion why this project is in this phase. Revert measure of speed like was in sr1sieve or sr2sieve.

Number of tested primes is less important then sieve depth. Also sieve depth show me immediately how sieve is deep, number of tested primes show me nothing. And when person do sieve, only important thing is sieve depth.

[QUOTE=pepi37;519306]And I have suggestion why this project is in this phase. Revert measure of speed like was in sr1sieve or sr2sieve.

Number of tested primes is less important then sieve depth. Also sieve depth show me immediately how sieve is deep, number of tested primes show me nothing. And when person do sieve, only important thing is sieve depth.[/QUOTE]

It shows the sieve depth and the rate. I do not understand the request.

I have posted 1.9.2. Here are the changes:
[LIST][*]Split makefile so only GPU-enabled code will compile and link with OpenCL libraries with intention of a single makefile in the future as having two nearly identical makefiles is difficult to maintain.[*]Made changes to the framework to support sieving in chunks as needed by gfndsieve and dmdsieve. [*]Added -x and -X switches to gfndsieve. With these switches one can execute Fermat divisibility checks after sieving.[*]Allow gfndsieve to sieve smaller n, but report if k*2^n+1 is a prime in the range being sieved. It will not report if k*2^n+1 is prime when k*2^n+1 > maxp, but less than maxp^2[*]Added -x and -X switches to dmdsieve. With these switches one can execute MMP divisibility checks after sieving.[/LIST]
With these changes gmp-fermat and gmp-double-mersenne are obsolete. The changes to gfndsieve and dmdsieve make them at least 50% faster than the aforementioned programs.

Although the srsieve2 code is included, it won't compile right now. I was in the middle of some refactoring when the changes above became higher priority. I'm out of town for two weeks, but hope to have time to get the srsieve pieces compiled and working again, which shouldn't be too hard. The sr2sieve/sr1sieve pieces need a lot more work.

[QUOTE=rogue;519494]Although the srsieve2 code is included, it won't compile right now. I was in the middle of some refactoring when the changes above became higher priority. I'm out of town for two weeks, but hope to have time to get the srsieve pieces compiled and working again, which shouldn't be too hard. The sr2sieve/sr1sieve pieces need a lot more work.[/QUOTE]

Could I ask, that the needed .dll files will be included in the mtsieve download file at sourceforge? It is not a high priority case, but eventually once sr1sieve and sr2sieve is implemented in the srsieve2 code, I most definently would like to use mtsieve on the Xeon. However the Xeon does not have the opencl environment installed and since the machine is not mine personally, it will not have opencl installed - hence mtsieve complaints about missing .dll files. What I´m asking is like we see it in the Prime95 fileset, a download file where all files needed to run mtsieve is in one file and a file where I do not have to go to unclear websites and retrieve a potentially bad .dll file - thank you.

[QUOTE=KEP;519808]Could I ask, that the needed .dll files will be included in the mtsieve download file at sourceforge? It is not a high priority case, but eventually once sr1sieve and sr2sieve is implemented in the srsieve2 code, I most definently would like to use mtsieve on the Xeon. However the Xeon does not have the opencl environment installed and since the machine is not mine personally, it will not have opencl installed - hence mtsieve complaints about missing .dll files. What I´m asking is like we see it in the Prime95 fileset, a download file where all files needed to run mtsieve is in one file and a file where I do not have to go to unclear websites and retrieve a potentially bad .dll file - thank you.[/QUOTE]

I assume you are referring to the OpenCL dlls. I will be updating the makefile so that the sieves not using OpenCL do not rely on them. As for the ones that do, I'll see what i can do.

[QUOTE=rogue;519814]I assume you are referring to the OpenCL dlls. I will be updating the makefile so that the sieves not using OpenCL do not rely on them. As for the ones that do, I'll see what i can do.[/QUOTE]

That is correct. I noticed that the k*fixed(b)^fixed(n)+/-c used the openCL dlls, but is srsieve2 once fully developed doesn't need the dlls, then I sure want be doing anything for years that would need the dlls - however they would be nice to have in the future since fbncsieve is very much faster compared to NewPGen and that would be nice to have in case I decide to start untested ranges in the future :smile: Thanks for your effort :smile:

How does one compile mtsieve on Linux? After downloading and extracting with "7za x", I get a ton of linker errors:

[code]$ make -f makefile.nogpu
g++ -Isieve -m64 -Wall -O2 -std=c++11 -lstdc++ -o afsieve core/App.o core/FactorApp.o core/AlgebraicFactorApp.o core/Clock.o core/Parser.o core/Worker.o core/HashTable.o core/main.o core/SharedMemoryItem.o sieve/Erat.o sieve/EratBig.o sieve/EratMedium.o sieve/EratSmall.o sieve/PreSieve.o sieve/CpuInfo.o sieve/MemoryPool.o sieve/PrimeGenerator.o sieve/PrimeSieve.o sieve/Wheel.o sieve/IteratorHelper.o sieve/popcount.o sieve/nthPrime.o sieve/PrintPrimes.o sieve/ParallelSieve.o sieve/iterator.o sieve/api.o sieve/SievingPrimes.o x86_asm/fpu_mod_init_fini.o x86_asm/fpu_push_pop.o x86_asm/fpu_mulmod.o x86_asm/fpu_powmod.o x86_asm/fpu_powmod_4b_1n_4p.o x86_asm/fpu_mulmod_iter.o x86_asm/fpu_mulmod_iter_4a.o x86_asm/fpu_mulmod_4a_4b_4p.o x86_asm/sse_mod_init_fini.o x86_asm/sse_powmod_4b_1n_4p.o x86_asm/sse_mulmod_4a_4b_4p.o x86_asm/avx_set_a.o x86_asm/avx_set_b.o x86_asm/avx_get.o x86_asm/avx_compute_reciprocal.o x86_asm/avx_compare.o x86_asm/avx_mulmod.o x86_asm/avx_powmod.o x86_asm/sse_powmod_4b_1n_4p_mulmod_1k.o alternating_factorial/AlternatingFactorialApp.o alternating_factorial/AlternatingFactorialWorker.o alternating_factorial/afsieve.o -lpthread
core/AlgebraicFactorApp.o:AlgebraicFactorApp.cpp:(.rdata$_ZTSSt9exception[_ZTSSt9exception]+0x0): multiple definition of `typeinfo name for std::exception'
core/AlgebraicFactorApp.o:AlgebraicFactorApp.cpp:(.rdata$_ZTISt9exception[_ZTISt9exception]+0x0): multiple definition of `typeinfo for std::exception'
core/AlgebraicFactorApp.o:AlgebraicFactorApp.cpp:(.rdata$_ZTSSt13runtime_error[_ZTSSt13runtime_error]+0x0): multiple definition of `typeinfo name for std::runtime_error'
core/AlgebraicFactorApp.o:AlgebraicFactorApp.cpp:(.rdata$_ZTISt13runtime_error[_ZTISt13runtime_error]+0x0): multiple definition of `typeinfo for std::runtime_error'
sieve/PrimeSieve.o:PrimeSieve.cpp:(.text$_ZNKSt5ctypeIcE8do_widenEc[_ZNKSt5ctypeIcE8do_widenEc]+0x0): multiple definition of `std::ctype<char>::do_widen(char) const'
...
alternating_factorial/AlternatingFactorialApp.o:AlternatingFactorialApp.cpp:(.text$_ZNSt6vectorIbSaIbEE14_M_fill_insertESt13_Bit_iteratoryb[_ZNSt6vectorIbSaIbEE14_M_fill_insertESt13_Bit_iteratoryb]+0x328): undefined reference to `operator new(unsigned long long)'
alternating_factorial/AlternatingFactorialWorker.o:AlternatingFactorialWorker.cpp:(.text$_ZN26AlternatingFactorialWorkerD0Ev[_ZN26AlternatingFactorialWorkerD0Ev]+0x25): undefined reference to `operator delete(void*, unsigned long long)'
core/App.o:App.cpp:(.xdata+0x14): undefined reference to `__gxx_personality_seh0'
core/App.o:App.cpp:(.xdata+0xd8): undefined reference to `__gxx_personality_seh0'
core/FactorApp.o:FactorApp.cpp:(.xdata+0x48): undefined reference to `__gxx_personality_seh0'
core/FactorApp.o:FactorApp.cpp:(.xdata+0x78): undefined reference to `__gxx_personality_seh0'
core/AlgebraicFactorApp.o:AlgebraicFactorApp.cpp:(.xdata+0x58): undefined reference to `__gxx_personality_seh0'
core/Worker.o:Worker.cpp:(.xdata+0x20): more undefined references to `__gxx_personality_seh0' follow[/code]

I have:

[code]$ g++ --version
g++ (Debian 7.3.0-18) 7.3.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.[/code]

[QUOTE=mathwiz;519911]How does one compile mtsieve on Linux? After downloading and extracting with "7za x", I get a ton of linker errors:

[code]$ make -f makefile.nogpu
g++ -Isieve -m64 -Wall -O2 -std=c++11 -lstdc++ -o afsieve core/App.o core/FactorApp.o core/AlgebraicFactorApp.o core/Clock.o core/Parser.o core/Worker.o core/HashTable.o core/main.o core/SharedMemoryItem.o sieve/Erat.o sieve/EratBig.o sieve/EratMedium.o sieve/EratSmall.o sieve/PreSieve.o sieve/CpuInfo.o sieve/MemoryPool.o sieve/PrimeGenerator.o sieve/PrimeSieve.o sieve/Wheel.o sieve/IteratorHelper.o sieve/popcount.o sieve/nthPrime.o sieve/PrintPrimes.o sieve/ParallelSieve.o sieve/iterator.o sieve/api.o sieve/SievingPrimes.o x86_asm/fpu_mod_init_fini.o x86_asm/fpu_push_pop.o x86_asm/fpu_mulmod.o x86_asm/fpu_powmod.o x86_asm/fpu_powmod_4b_1n_4p.o x86_asm/fpu_mulmod_iter.o x86_asm/fpu_mulmod_iter_4a.o x86_asm/fpu_mulmod_4a_4b_4p.o x86_asm/sse_mod_init_fini.o x86_asm/sse_powmod_4b_1n_4p.o x86_asm/sse_mulmod_4a_4b_4p.o x86_asm/avx_set_a.o x86_asm/avx_set_b.o x86_asm/avx_get.o x86_asm/avx_compute_reciprocal.o x86_asm/avx_compare.o x86_asm/avx_mulmod.o x86_asm/avx_powmod.o x86_asm/sse_powmod_4b_1n_4p_mulmod_1k.o alternating_factorial/AlternatingFactorialApp.o alternating_factorial/AlternatingFactorialWorker.o alternating_factorial/afsieve.o -lpthread
core/AlgebraicFactorApp.o:AlgebraicFactorApp.cpp:(.rdata$_ZTSSt9exception[_ZTSSt9exception]+0x0): multiple definition of `typeinfo name for std::exception'
core/AlgebraicFactorApp.o:AlgebraicFactorApp.cpp:(.rdata$_ZTISt9exception[_ZTISt9exception]+0x0): multiple definition of `typeinfo for std::exception'
core/AlgebraicFactorApp.o:AlgebraicFactorApp.cpp:(.rdata$_ZTSSt13runtime_error[_ZTSSt13runtime_error]+0x0): multiple definition of `typeinfo name for std::runtime_error'
core/AlgebraicFactorApp.o:AlgebraicFactorApp.cpp:(.rdata$_ZTISt13runtime_error[_ZTISt13runtime_error]+0x0): multiple definition of `typeinfo for std::runtime_error'
sieve/PrimeSieve.o:PrimeSieve.cpp:(.text$_ZNKSt5ctypeIcE8do_widenEc[_ZNKSt5ctypeIcE8do_widenEc]+0x0): multiple definition of `std::ctype<char>::do_widen(char) const'
...
alternating_factorial/AlternatingFactorialApp.o:AlternatingFactorialApp.cpp:(.text$_ZNSt6vectorIbSaIbEE14_M_fill_insertESt13_Bit_iteratoryb[_ZNSt6vectorIbSaIbEE14_M_fill_insertESt13_Bit_iteratoryb]+0x328): undefined reference to `operator new(unsigned long long)'
alternating_factorial/AlternatingFactorialWorker.o:AlternatingFactorialWorker.cpp:(.text$_ZN26AlternatingFactorialWorkerD0Ev[_ZN26AlternatingFactorialWorkerD0Ev]+0x25): undefined reference to `operator delete(void*, unsigned long long)'
core/App.o:App.cpp:(.xdata+0x14): undefined reference to `__gxx_personality_seh0'
core/App.o:App.cpp:(.xdata+0xd8): undefined reference to `__gxx_personality_seh0'
core/FactorApp.o:FactorApp.cpp:(.xdata+0x48): undefined reference to `__gxx_personality_seh0'
core/FactorApp.o:FactorApp.cpp:(.xdata+0x78): undefined reference to `__gxx_personality_seh0'
core/AlgebraicFactorApp.o:AlgebraicFactorApp.cpp:(.xdata+0x58): undefined reference to `__gxx_personality_seh0'
core/Worker.o:Worker.cpp:(.xdata+0x20): more undefined references to `__gxx_personality_seh0' follow[/code]

I have:

[code]$ g++ --version
g++ (Debian 7.3.0-18) 7.3.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.[/code][/QUOTE]
Run "make -f makefile.nogpu clean" first

The most likely issue is the version of gcc you are using. Can you update it?

Is it linking to gmp and gmpxx? I am a bit surprised there is no -lgmp or -lgmpxx on that g++ line

[QUOTE=henryzz;519924]Is it linking to gmp and gmpxx? I am a bit surprised there is no -lgmp or -lgmpxx on that g++ line[/QUOTE]

Only dmdsieve and gfndsieve require gmp.

[QUOTE=rogue;519494]I have posted 1.9.2. Here are the changes:
With these changes gmp-fermat and gmp-double-mersenne are obsolete. The changes to gfndsieve and dmdsieve make them at least 50% faster than the aforementioned programs.[/QUOTE]

The table at [url]http://www.fermatsearch.org/productivity.html[/url] still shows GMP-Fermat as significantly faster than gfndsieve+pfgw for n <= 1000. Is this accurate, or does the table need to be updated?

[QUOTE=mathwiz;520490]The table at [url]http://www.fermatsearch.org/productivity.html[/url] still shows GMP-Fermat as significantly faster than gfndsieve+pfgw for n <= 1000. Is this accurate, or does the table need to be updated?[/QUOTE]

Mike, Gary and I are working on a possible benchmarking suite, as there are just too many variables in play while trying to define the efficiency of each program before all the others.

In other words, the benchmark page gives a rough idea of the efficiency, but should not be taken as liquid gold.

[QUOTE=ET_;520525]Mike, Gary and I are working on a possible benchmarking suite, as there are just too many variables in play while trying to define the efficiency of each program before all the others.

In other words, the benchmark page gives a rough idea of the efficiency, but should not be taken as liquid gold.[/QUOTE]

Just as example, gfndsieve is faster than GMP-Fermat, but GMP-Fermat can work on larger gaps than gfndsieve at once.

[QUOTE=mathwiz;520490]The table at [url]http://www.fermatsearch.org/productivity.html[/url] still shows GMP-Fermat as significantly faster than gfndsieve+pfgw for n <= 1000. Is this accurate, or does the table need to be updated?[/QUOTE]

It is accurate. The problem is the overhead added by pfgw really hurts throughput for smaller n.

[QUOTE=ET_;520526]Just as example, gfndsieve is faster than GMP-Fermat, but GMP-Fermat can work on larger gaps than gfndsieve at once.[/QUOTE]

What do you mean by "larger gaps"?

[QUOTE=rogue;520547]What do you mean by "larger gaps"?[/QUOTE]

Gaps that make gfndsieve memory dump.

[QUOTE=ET_;520550]Gaps that make gfndsieve memory dump.[/QUOTE]

Are you referring to cases where -X is too large? As long as -X is reasonably set, gnfdsieve should not crash.

[QUOTE=rogue;520557]Are you referring to cases where -X is too large? As long as -X is reasonably set, gnfdsieve should not crash.[/QUOTE]

No, the dump happened with the -x switch (not -X), small N and a very large k range

[QUOTE=ET_;520561]No, the dump happened with the -x switch (not -X), small N and a very large k range[/QUOTE]

-X defaults to 1e10, so it will take slightly over 1 GB of memory to run. If you use -X to set to a smaller value, will it run? If not, please let me know the range for k and n. Maybe there is a different bug that needs to be fixed.

[QUOTE=rogue;520567]-X defaults to 1e10, so it will take slightly over 1 GB of memory to run. If you use -X to set to a smaller value, will it run? If not, please let me know the range for k and n. Maybe there is a different bug that needs to be fixed.[/QUOTE]

[code]
./gfndsieve -n 120 -N 121 -k 1200000000000000 -K 1300000000000000 -P 1e9 -x
gfndsieve v1.6, a program to find factors of k*2^n+1 numbers for variable k and n
Errore di segmentazione (core dump creato)
[/code]

[QUOTE=ET_;520575][code]
./gfndsieve -n 120 -N 121 -k 1200000000000000 -K 1300000000000000 -P 1e9 -x
gfndsieve v1.6, a program to find factors of k*2^n+1 numbers for variable k and n
Errore di segmentazione (core dump creato)
[/code][/QUOTE]

I found a bug in the code and will be fixed in the next release. For now sieve a single n at a time instead of multiple n.

[QUOTE=rogue;520580]I found a bug in the code and will be fixed in the next release. For now sieve a single n at a time instead of multiple n.[/QUOTE]

Thank you Mike .

I found a bug for xyyxsieve. When testing for the + form (ie x^y + y^x) the header it spits out in the output file is


[CODE]ABC $a^$b$c$b^$a[/CODE]which looks right, however when pfgw is used to test this, it yields the following, for example:


[CODE]105^1828+11828^105[/CODE]which comes from the line



[CODE]105 1828 +1[/CODE]in the file. However, the actual number that should be tested is 105^1828+1828^105. So the header is incorrect. This can be fixed (I think) by changing line 324 of XYYXApp.cpp from


[CODE]fprintf(fPtr, "ABC $a^$b$c$b^$a // Sieved to %" PRIu64"\n", largestPrime);[/CODE]to


[CODE]fprintf(fPtr, "ABC $a^$b$c*$b^$a // Sieved to %" PRIu64"\n", largestPrime);[/CODE]
If it helps with debugging, the command line I used was xyyxsieve -P 1e8 -W 12 -s + -x 100 -X 200 -y 1000 -Y 2000 -o test.

[QUOTE=Dylan14;522260]I found a bug for xyyxsieve. When testing for the + form (ie x^y + y^x) the header it spits out in the output file is


[CODE]ABC $a^$b$c$b^$a[/CODE]which looks right, however when pfgw is used to test this, it yields the following, for example:


[CODE]105^1828+11828^105[/CODE]which comes from the line



[CODE]105 1828 +1[/CODE]in the file. However, the actual number that should be tested is 105^1828+1828^105. So the header is incorrect. This can be fixed (I think) by changing line 324 of XYYXApp.cpp from


[CODE]fprintf(fPtr, "ABC $a^$b$c$b^$a // Sieved to %" PRIu64"\n", largestPrime);[/CODE]to


[CODE]fprintf(fPtr, "ABC $a^$b$c*$b^$a // Sieved to %" PRIu64"\n", largestPrime);[/CODE]
If it helps with debugging, the command line I used was xyyxsieve -P 1e8 -W 12 -s + -x 100 -X 200 -y 1000 -Y 2000 -o test.[/QUOTE]

Thanks for the report. I'll fix it.

I am releasing mtsieve 1.9.3. Here are the changes:
[list][*]Re-implemented a single makefile. It will now build separate exes for OpenCL enabled binaries.[*]Fix ABC format line in xyyxsieve output file.[*]Adjust reported factoring rate to account for less than 1 full CPU or more than 1 full CPU.[*]Handle race condition that can trigger an infinite loop.[*]Allow the first chunk to be smaller so that a rebuild of terms can be triggered earlier.[*]srsieve2 will compile, but requires more testing and only has srsieve functions.[/list]
I haven't seen any issues with srsieve2. Of course that doesn't mean that there aren't any. Please run alongside srsieve/sr2sieve if you use it. For most bases it is about 40% faster than srsieve, but for others it is a wash. I'm not certain why, but I suspect it has something to do with cache hits and misses.

Mark, I am doing some benchmarking of gfndsieve (mtsieve 1.9.3) with various values of N. When I run a range of K that is greater than the default -X size, the program seems to go into an infinite loop. See below. At the point that it prints "Sieve started" the second time, the CPU utilization shown by top drops from ~100% to <1%. Not sure if this is related to the problem reported by Luigi or not. If I add -X 2e10 it works correctly, so for now I have a workaround at the cost of more memory.

Also a suggestion: When using -x, would it be possible for gfndsieve to set the default pmax value as a function of N so as to minimize the total runtime? Currently I am just guessing at the best pmax for each N based on some testing at N = 1000. The optimal pmax there is about 5e9, which is much less than the current default of 2^62.

Thanks!
[code]
Omen-Linux: /usr/bin/time gfndsieve -n 29 -N 29 -k 50000000000000001 -K 50000020000000000 -x -W 1 -P 50000000
gfndsieve v1.6, a program to find factors of k*2^n+1 numbers for variable k and n
Sieve started: 3 < p < 5e7 with 10000000000 terms (50000000000000001 <= k <= 50000010000000002, 29 <= n <= 29, k*2^n+1) (expecting 9380279109 factors)
p=419, 1.321 p/sec, 4084567559 factors found at 66.29M f/sec, 0.0% done. ETC 2019-10-28 09:46
p=255917, 367.8 p/sec, 4549217009 factors found at 37.09M f/sec, 0.5% done. ETC 2019-08-04 19:48

Sieve completed at p=50000047.
Processor time: 165.37 sec. (0.01 sieving) (1.00 cores)
Primes tested: 3001136. Factors found: 4683516745. Remaining terms: 5316483255. Time: 165.21 seconds.
Tested 37.76 pct of range at 61901906 terms per second (53.16 pct terms passed sieving)
Tested 50.00 pct of range at 40816326 terms per second (53.16 pct terms passed sieving)

Sieve started: 3 < p < 5e7 with 4999999999 terms (50000010000000002 <= k <= 50000019999999999, 29 <= n <= 29, k*2^n+1) (expecting 4690139554 factors)
p=50000047, 49.30K p/sec, no factors found, 100.0% done. ETC 2019-08-04 13:16
p=50000047, 0.000 p/sec, no factors found, 100.0% done. ETC 2019-08-04 13:17
p=50000047, 0.000 p/sec, no factors found, 100.0% done. ETC 2019-08-04 13:18
p=50000047, 0.000 p/sec, no factors found, 100.0% done. ETC 2019-08-04 13:19
p=50000047, 0.000 p/sec, no factors found, 100.0% done. ETC 2019-08-04 13:20

... never ends ...

[/code]

[QUOTE=Gary;523093]Mark, I am doing some benchmarking of gfndsieve (mtsieve 1.9.3) with various values of N. When I run a range of K that is greater than the default -X size, the program seems to go into an infinite loop. See below. At the point that it prints "Sieve started" the second time, the CPU utilization shown by top drops from ~100% to <1%. Not sure if this is related to the problem reported by Luigi or not. If I add -X 2e10 it works correctly, so for now I have a workaround at the cost of more memory.

Also a suggestion: When using -x, would it be possible for gfndsieve to set the default pmax value as a function of N so as to minimize the total runtime? Currently I am just guessing at the best pmax for each N based on some testing at N = 1000. The optimal pmax there is about 5e9, which is much less than the current default of 2^62.

Thanks!
[code]
Omen-Linux: /usr/bin/time gfndsieve -n 29 -N 29 -k 50000000000000001 -K 50000020000000000 -x -W 1 -P 50000000
gfndsieve v1.6, a program to find factors of k*2^n+1 numbers for variable k and n
Sieve started: 3 < p < 5e7 with 10000000000 terms (50000000000000001 <= k <= 50000010000000002, 29 <= n <= 29, k*2^n+1) (expecting 9380279109 factors)
p=419, 1.321 p/sec, 4084567559 factors found at 66.29M f/sec, 0.0% done. ETC 2019-10-28 09:46
p=255917, 367.8 p/sec, 4549217009 factors found at 37.09M f/sec, 0.5% done. ETC 2019-08-04 19:48

Sieve completed at p=50000047.
Processor time: 165.37 sec. (0.01 sieving) (1.00 cores)
Primes tested: 3001136. Factors found: 4683516745. Remaining terms: 5316483255. Time: 165.21 seconds.
Tested 37.76 pct of range at 61901906 terms per second (53.16 pct terms passed sieving)
Tested 50.00 pct of range at 40816326 terms per second (53.16 pct terms passed sieving)

Sieve started: 3 < p < 5e7 with 4999999999 terms (50000010000000002 <= k <= 50000019999999999, 29 <= n <= 29, k*2^n+1) (expecting 4690139554 factors)
p=50000047, 49.30K p/sec, no factors found, 100.0% done. ETC 2019-08-04 13:16
p=50000047, 0.000 p/sec, no factors found, 100.0% done. ETC 2019-08-04 13:17
p=50000047, 0.000 p/sec, no factors found, 100.0% done. ETC 2019-08-04 13:18
p=50000047, 0.000 p/sec, no factors found, 100.0% done. ETC 2019-08-04 13:19
p=50000047, 0.000 p/sec, no factors found, 100.0% done. ETC 2019-08-04 13:20

... never ends ...

[/code][/QUOTE]

Thanks for the bug report. I'll take a look. It will probably be something really simple.

To limit pmax based upon nmax would require a table. If someone could come up with a list mapping n to p, that would save me a lot of time.

[QUOTE]To limit pmax based upon nmax would require a table. If someone could come up with a list mapping n to p, that would save me a lot of time.[/QUOTE]
I can test several of the Ns in the FermatSearch Productivity table and determine a ball-park optimal value of pmax. Will take a few days.

I tracked down the problem. Do you need the fix?

[QUOTE=rogue;523145]I tracked down the problem. Do you need the fix?[/QUOTE]
It's not urgent. I can wait for the next release. I have determined the optimal pmax for n from 40 to 10k, and have a run going now for up to 100k. I should be able to send you a table in a day or so, then maybe that and the fix could be the next release.

[QUOTE=Gary;523257]It's not urgent. I can wait for the next release. I have determined the optimal pmax for n from 40 to 10k, and have a run going now for up to 100k. I should be able to send you a table in a day or so, then maybe that and the fix could be the next release.[/QUOTE]

Sounds good. Thanks for your contribution.

Here are the optimal pmax values I found for various values of n:

[CODE]
n pmax
40 3e06
60 1e08
80 1e09
100 1e09
150 1e09
200 1e09
300 3e09
400 3e09
600 1e10
800 1e10
1000 1e10
2000 1e10
3000 1e10
5000 3e10
10000 3e10
20000 3e10
30000 3e10
50000 3e10
100000 3e10
[/CODE]For each n I measured execution time over a range of pmax that was 100x to 1000x (smallest pmax to largest pmax), and then adjusted the range until I saw a local minimum at the center of the range. For each n, I chose a range of k that was close to the current search wavefront. A typical run is shown below. Let me know if you want me to find the optimal pmax for any other n's.

For n <= 100 gfndsieve -x appears to be slower than GMP-Fermat (fermat64_redc). See below for n=40 with both programs using about 500K primes. Is this what you would expect, or are there some parameters for gfndsieve that I should set differently to get best performance?
[CODE]
Omen-Linux: cat fermat.ini
nStart=40
nEnd=40
kStart=50000000000000001
kEnd=50000017000000000
Omen-Linux: /usr/bin/time fermat64_redc
GMP-Fermat version 2.5

The value FilterPrimes was not set, it will default to 500000.
Processing range of k from 50000000000000001 to 50000017000000000 and range of n from 40 to 40

Testing for n = 40
Tested to 50000014834221031 (tested 3.55 pct candidates) at 81286434 per second
Overall rate for n=40: tested 603673601 of 17000000000 numbers ( 3.55 pct) in 209.10 seconds at 81299377 k per second

Done
209.15user 0.00system 3:29.15elapsed 99%CPU (0avgtext+0avgdata 11136maxresident)k
0inputs+32outputs (0major+4000minor)pagefaults 0swaps


Omen-Linux: /usr/bin/time gfndsieve -n 40 -N 40 -k 50000000000000001 -K 50000017000000000 -x -X 20000000000 -W 1 -P 74e5
gfndsieve v1.6, a program to find factors of k*2^n+1 numbers for variable k and n
Sieve started: 3 < p < 74e5 with 8500000000 terms (50000000000000001 <= k <= 50000016999999999, 40 <= n <= 40, k*2^n+1) (expecting 7909609279 factors)
p=23, 0.133 p/sec, 5866227649 factors found at 94.15M f/sec, 0.0% done. ETC 2020-04-28 14:59
p=4759, 10.36 p/sec, 7375468757 factors found at 59.80M f/sec, 0.1% done. ETC 2019-08-13 14:16
p=229399, 323.6 p/sec, 7726883695 factors found at 15.13M f/sec, 3.1% done. ETC 2019-08-11 11:11

Sieve completed at p=7400023.
Processor time: 230.93 sec. (0.01 sieving) (1.00 cores)
Primes tested: 501964. Factors found: 7896495619. Remaining terms: 603504381. Time: 230.30 seconds.
Tested 32.78 pct of range at 40978506 terms per second ( 7.10 pct terms passed sieving)
Tested 65.59 pct of range at 40842360 terms per second ( 7.10 pct terms passed sieving)
Tested 98.39 pct of range at 40897250 terms per second ( 7.10 pct terms passed sieving)
Tested 100.00 pct of range at 40865384 terms per second ( 7.10 pct terms passed sieving)
416.53user 0.38system 6:56.97elapsed 99%CPU (0avgtext+0avgdata 2453548maxresident)k
0inputs+16outputs (0major+612545minor)pagefaults 0swaps
[/CODE]A few other issues I ran into using gfndsieve that you may want to address in the next release:

1) When I first ran "make gfndsieve", during the load phase I got an undefined reference error for all of the pthreads functions.
I noticed you already have "EXTRALDFLAGS+=-lpthread" in the makefile but were not using it, so I added $(EXTRALDFLAGS)
to the end of the build line for gfndsieve. Seems this would need to be added to many of the other binaries also, or you may have
a different fix in mind.

2) If I time gfndsieve and redirect stdout and stderr to a file, the time output overwrites the last output line of gfndsieve.
See below. I worked around this in App.cpp WriteToConsole by changing the printf("\r") to printf("\n"). This eliminates the status line
overwrite completely, which is fine/preferred when redirecting output, but probably not what you want in general.

[CODE]Omen-Linux: /usr/bin/time gfndsieve -n 1000 -N 1000 -k 300000000001 -K 300060000000 -x -X 1e10 -W 1 -P 5000000000 >& out
Omen-Linux: cat out
gfndsieve v1.6, a program to find factors of k*2^n+1 numbers for variable k and n
Sieve started: 3 < p < 5e9 with 30000000 terms (300000000001 <= k <= 300059999999, 1000 <= n <= 1000, k*2^n+1) (expecting 28524211 factors)
Sieve completed at p=5000000039.
Processor time: 9.84 sec. (0.72 sieving) (0.82 cores)
Primes tested: 234954224. Factors found: 28492833. Remaining terms: 1507167. Time: 12.03 seconds.
348.75user 0.18system 5:51.47elapsed 99%CPU (0avgtext+0avgdata 1233304maxresident)kng)
0inputs+64outputs (0major+307780minor)pagefaults 0swaps[/CODE]

I would expect that each program would have a different optimal sieve depth for a given n to reach maximum throughput.

[QUOTE=rogue;523525]I would expect that each program would have a different optimal sieve depth for a given n to reach maximum throughput.[/QUOTE]
Yes, agreed. The point I was trying to make (maybe poorly) was that even when I use the pmax that maximizes throughput of gfndsieve at n=40, it is still only half the throughput of GMP-Fermat. Once I get your -X fix I will try larger ranges of K with smaller chunk sizes to see if that improves throughput.

Thanks!

I try to compile latest mtsieve under Linux and failed with many errors. On same machine I can compile 1.9. without any problem: so it looks like problem appear on latest few revision.

[QUOTE=pepi37;523796]I try to compile latest mtsieve under Linux and failed with many errors. On same machine I can compile 1.9. without any problem: so it looks like problem appear on latest few revision.[/QUOTE]

PM me with the output from the build.

I have posted 1.9.4. The changes are:
[LIST][*]Fix a segfault with srsieve2 when rebuilding subsequences.[*]Fix a segfault with AVX logic on non-Windows OSes.[*]Fixed an issue with gfndsieve and dmdsieve where a large range of k and small range of x cause it to not sieve subsequent subranges.[*]Added a table to gfndsieve to pre-set pmax if using -x and -P is not specified.[*]Add -D flag to xyyxsieve to disable AVX as it crashes in the AVX routines on Windows OS on AMD CPUs. The flag will be removed when that issue is resolved, but I need someone with an AMD CPU to figure it out as I don't have one. Other sieves using AVX might have the same issue. I'll add -D to them if they have the problem and I'm asked to fix.[*]Added -fP to srsieve2. This will generate a more verbose ABC output file with each line specificing the values of k, n, and c. It will also add the number_primes switch which is supported by pfgw to ensure only a single prime for each distinct k of the file.[*]Added -fB to srsieve2. This will generate a format that can be used to load BOINC. This is equivalent to the "PRP" format used by srsieve/srfile[/LIST]
I have not tested the -fB option for srsieve2 as it was a late addition.

-FB is not working in srsieve2, gives me an error message with -f B, the program recognize a space between FB but there isnt one.

[QUOTE=rogue;523836]I have posted 1.9.4. The changes are:
[LIST][*]Fix a segfault with srsieve2 when rebuilding subsequences.[*]Fix a segfault with AVX logic on non-Windows OSes.[*]Fixed an issue with gfndsieve and dmdsieve where a large range of k and small range of x cause it to not sieve subsequent subranges.[*]Added a table to gfndsieve to pre-set pmax if using -x and -P is not specified.[*]Add -D flag to xyyxsieve to disable AVX as it crashes in the AVX routines on Windows OS on AMD CPUs. The flag will be removed when that issue is resolved, but I need someone with an AMD CPU to figure it out as I don't have one. Other sieves using AVX might have the same issue. I'll add -D to them if they have the problem and I'm asked to fix.[*]Added -fP to srsieve2. This will generate a more verbose ABC output file with each line specificing the values of k, n, and c. It will also add the number_primes switch which is supported by pfgw to ensure only a single prime for each distinct k of the file.[*]Added -fB to srsieve2. This will generate a format that can be used to load BOINC. This is equivalent to the "PRP" format used by srsieve/srfile[/LIST]
I have not tested the -fB option for srsieve2 as it was a late addition.[/QUOTE]


This build is compiled without error but I must install before compiling libgmp-dev package ( under Debian) because I got error: fatal error: no gmp.h
But after installing package all is OK!
Thanks!

Compiling is ok but there is no twinsieve , srsieve2 and xyyxsieve

[QUOTE=rebirther;523837]-FB is not working in srsieve2, gives me an error message with -f B, the program recognize a space between FB but there isnt one.[/QUOTE]

I'm confused. Are you using -F or -f? -F is not a switch, but -f is.

[QUOTE=pepi37;523853]This build is compiled without error but I must install before compiling libgmp-dev package ( under Debian) because I got error: fatal error: no gmp.h
But after installing package all is OK!
Thanks!

Compiling is ok but there is no twinsieve , srsieve2 and xyyxsieve[/QUOTE]

If you use one of these commands: "make twinsieve", "make srsieve2", or
"make xyyxsieve", what happens?

Not sure if this is a bug or not, but I am trying to sieve the gap


[CODE]n 4900-4999 7e8-10e8[/CODE]in gfndsieve for someone to test for the FermatSearch. However, it seems that gfndsieve is having a bit of trouble with this range:


[CODE]C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>gfndsieve -W 12 -P 1e10 -n 4900 -N 4999 -k 7e8 -K 10e8
gfndsieve v1.6, a program to find factors of k*2^n+1 numbers for variable k and n
Sieve started: 3 < p < 1e10 with 15000000000 terms (700000001 <= k <= 999999999, 4900 <= n <= 4999, k*2^n+1) (expecting 14284318118 factors)
p=5353556269, 4.022M p/sec, 14222420430 factors found at 947.2K f/sec, 53.5% done. ETC 2019-08-18 11:14
Sieve completed at p=10000000033.
Processor time: 1387.59 sec. (5.11 sieving) (2.47 cores)
Fatal Error: Something is wrong. Counted terms (731497142) != expected terms (757534783)[/CODE]Even cutting the amount of k's tested from 3e8 to 1e8 doesn't help:


[CODE]C:\Users\Dylan\Desktop\prime finding\sieves\mtsieve>gfndsieve -W 12 -P 1e10 -n 4900 -N 4999 -k 7e8 -K 8e8
gfndsieve v1.6, a program to find factors of k*2^n+1 numbers for variable k and n
Sieve started: 3 < p < 1e10 with 5000000000 terms (700000001 <= k <= 799999999, 4900 <= n <= 4999, k*2^n+1) (expecting 4761439373 factors)
p=737410679, 553.0K p/sec, 4715578537 factors found at 1.089M f/sec, 7.4% done. ETC 2019-08-18 11:49
Sieve completed at p=10000000033.
Processor time: 611.70 sec. (3.94 sieving) (3.03 cores)
Fatal Error: Something is wrong. Counted terms (243821033) != expected terms (249825410)[/CODE]I thought that it could be a problem with the computer writing all the terms to disk, but I dismissed that as the computer I'm testing this on has a NVMe SSD, which is fast, and that I have done smaller ranges at higher n values with no problems. What could be the issue here?

[QUOTE=rogue;523868]I'm confused. Are you using -F or -f? -F is not a switch, but -f is.[/QUOTE]

[CODE]n:\riesel-base537 - Kopie>srsieve2 -n2501 -N10000 -P1e9 -spl_remain.txt -fB
srsieve2 v1.1, a program to find factors of k*b^n+c numbers for fixed b and vari
able k and n
Fatal Error: srsieve2: invalid argument -f B[/CODE]

[QUOTE=rogue;523869]If you use one of these commands: "make twinsieve", "make srsieve2", or
"make xyyxsieve", what happens?[/QUOTE]

make twinsieve works ok and produce twinsieve, and also xyyxsieve



make srsieve2


make srsieve2
make: *** No rule to make target 'sierpinksi_riesel/SierpinskiRieselApp.o', needed by 'srsieve2'. Stop.

[QUOTE=Dylan14;523870]Not sure if this is a bug or not, but I am trying to sieve the gap


[CODE]n 4900-4999 7e8-10e8[/CODE]in gfndsieve for someone to test for the FermatSearch. However, it seems that gfndsieve is having a bit of trouble with this range:

(some output involving term numbers not matching)
[/QUOTE]


I figured the problem out. The sieve has to start as a single thread process and then after the initial sieve is done, then multiple threads can be used.

[QUOTE=pepi37;523872]make twinsieve works ok and produce twinsieve, and also xyyxsieve



make srsieve2


make srsieve2
make: *** No rule to make target 'sierpinksi_riesel/SierpinskiRieselApp.o', needed by 'srsieve2'. Stop.[/QUOTE]

Sorry, but that is due to a misspelling in the path. I correctly the misspelling of the folder name, but didn't save the change to the makefile. It should be "sierpinski_riesel" not "sierpinksi_riesel" in the makefile. Fix that and you should be able to build.

[QUOTE=Dylan14;523877]I figured the problem out. The sieve has to start as a single thread process and then after the initial sieve is done, then multiple threads can be used.[/QUOTE]

A number of sieves, due to the high percentage of terms removed with the initial block of primes, only run a single thread for that block an in effort to avoid some of of the throttling that occurs when multiple threads try to access the same memory.

To get to multiple threads more quickly, use -w to specify smaller chunks of primes.

I posted version 1.9.5 of the framework. The only change is that I fixed the factor rate calculation.

[QUOTE=rogue;524767]I posted version 1.9.5 of the framework. The only change is that I fixed the factor rate calculation.[/QUOTE]

I ran make and found:

#include "CIsOneSubsequenceHelper.h" - the correct file name is CisOneSubsequenceHelper.h

dm_divisor/DMDivisorApp.cpp
gfn_divisor/GFNDivisorApp.cpp
fixed_bnc/FixedBNCApp.cpp
fixed_kbn/FixedKBNApp.cpp
kbb/KBBApp.cpp
sierpinski_riesel/SierpinskiRieselApp.cpp
twin/TwinApp.cpp
ALL have wrong permissions (I had to chmod 666 to them)

core/../opencl/Device.h:19:13: fatal error: CL/cl.h: File or directory not existing
And setting ENABLE_GPU=no does not work either.

Luigi

[QUOTE=ET_;524782]I ran make and found:

#include "CIsOneSubsequenceHelper.h" - the correct file name is CisOneSubsequenceHelper.h

dm_divisor/DMDivisorApp.cpp
gfn_divisor/GFNDivisorApp.cpp
fixed_bnc/FixedBNCApp.cpp
fixed_kbn/FixedKBNApp.cpp
kbb/KBBApp.cpp
sierpinski_riesel/SierpinskiRieselApp.cpp
twin/TwinApp.cpp
ALL have wrong permissions (I had to chmod 666 to them)

core/../opencl/Device.h:19:13: fatal error: CL/cl.h: File or directory not existing
And setting ENABLE_GPU=no does not work either.

Luigi[/QUOTE]

I'll fix that spelling. Windows doesn't care but OS X and Linux do.

Since the .7z file is created on Windows, I don't know how its permissions correspond to permissions on Linux.

The ENABLE_GPU flag is removed from the makefile. If you have a GPU, then you will need to install an OpenCL SDK. You also might need to modify the GPUCPPFLAGS and GPULDFLAGS in the makefile.

If you do not have a GPU, then use "make cpu_all". It will no build the OpenCL versions of the exes.