mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Software (https://www.mersenneforum.org/forumdisplay.php?f=10)

 MischaR 2023-04-27 10:29

I came across a couple of bugs when using srsieve2 on 'uncommon' c values:

Using srsieve2 version 1.7
[QUOTE]
.\srsieve2_1.7.exe -P 1e12 -n 1 -N 10000 -s "1*10^n+21"
srsieve2 v1.7, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Must use generic sieving logic because abs(c) != 1 for at least one sequence
Sieving with generic logic for p >= 3
Sieve started: 3 < p < 1e12 with 10000 terms (1 < n < 10000, k*10^n+21) (expecting 9602 factors)
Fatal Error: Invalid factor: 1*10^2+21 mod 11 = 11
[/QUOTE]
Now I'm no maths expert but I'm pretty sure anything mod 11 can never equal 11 :p

This also happens for the following forms I was trying to sieve:
1*10^n+19: "Fatal Error: Invalid factor: 1*10^2+19 mod 7 = 14"
1*10^n+91: "Fatal Error: Invalid factor: 1*10^13+91 mod 17 = 85"
9*10^n+11: "Fatal Error: Invalid factor: 9*10^5+11 mod 7 = 7"
78*10^n+217: "Fatal Error: Invalid factor: 78*10^3+217 mod 17 = 204"

Same for 1*10^n+7, 1*10^n+9, 1*10^n+11 etc. Weirdly enough, it seems to only happen when C is positive. I'm yet to come across a form with larger negative C's that also cause these issues.
One could argue that srsieve2 is meant for Sierpinski/Riesel primes, so any C besides +1 or -1 is out of scope, but I've sieved dozens of other forms with srsieve2 where C doesn't equals +1 or -1 and that works fine

A different bug was found for form 7*10^n+1:
[QUOTE]
.\srsieve2_1.7.exe -o "output-k7.txt" -P 1e12 -n 1 -N 10000 -s "7*10^n+1"
srsieve2 v1.7, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Sieving with generic logic for p >= 3
Sieve started: 3 < p < 1e12 with 10000 terms (1 < n < 10000, k*10^n+1) (expecting 9602 factors)
7*10^1+1 is prime!
7*10^2+1 is prime!
Sieving with single sequence c=1 logic for p >= 257
BASE_MULTIPLE = 30, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720
Split 1 base 10 sequence into 30 base 10^30 sequences.
Legendre summary: Approximately 36 bytes needed for Legendre tables
1 total sequences
1 are eligible for Legendre tables
0 are not eligible for Legendre tables
0 have Legendre tables in memory
1 cannot have Legendre tables in memory
0 have Legendre tables loaded from files
0 required building of the Legendre tables
Assertion failed: qListLen < ii_BestQ, file sierpinski_riesel/CisOneWithOneSequenceHelper.cpp, line 230
[/QUOTE]
srsieve2 then exits, and no output file is written

 rogue 2023-04-27 14:25

[QUOTE=MischaR;629490]I came across a couple of bugs when using srsieve2 on 'uncommon' c values[/QUOTE]

Thanks for the bug report. Both of these will be fixed in the next release.

 storm5510 2023-04-27 15:04

[QUOTE=rogue;629442]Interesting. You typically only need to set -M for initial sieving due to higher factor density. How many combinations of -g and -G have you played with? What if you use -g128 or -g256 without -G?[/QUOTE]

I will have to try that. I made the assumption that [I]-g[/I] and [I]-G[/I] had to be used together, or neither.

How many combinations of -[I]g[/I] and -[I]G[/I] have I played with? Not many, and nowhere near the size stated above.
---
I just tried [I]-g256[/I] without [I]-G[/I]. It does alright on this machine. 430K p/sec. On an older machine with a 1080, [I]srsievecl[/I] really slows. That system has a proprietary 500W PSU. I have to throttle it or it will reboot itself. [I]srsieve2[/I] runs well on it. 404K p/sec with Lengendre tables. A good CPU. I can't complain.

 rebirther 2023-05-03 15:45

I have noticed that srsieve2 v1.7 is slower than 1.6.3 and have more remaining terms (this is a test only with 2 factors):

[CODE]g:\>srsieve2 -n2501 -N10000 -P1e10 -W16 -spl_remain.txt
srsieve2 v1.7, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Must use generic sieving logic because -l was not specified for mutiple sequences
Sieving with generic logic for p >= 3
Sieve started: 3 < p < 1e10 with 15000 terms (2501 < n < 10000, k*822^n+1) (expecting 14284 factors)
Sieving with generic logic for p >= 822
Split 2 base 822 sequences into 15 base 822^12 sequences.
Increasing worksize to 2000000 since each chunk is tested in less than a second
Sieve completed at p=10000000033.
CPU time: 741.56 sec. (3.00 sieving) (14.81 cores)
1152 terms written to b822_n.abcd
Primes tested: 455052224. Factors found: 13848. Remaining terms: 1152. Time: 50.08 seconds.[/CODE]

[CODE]g:\>srsieve2 -n2501 -N10000 -P1e10 -W16 -spl_remain.txt
srsieve2 v1.6.3, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Will use generic sieving logic because no memory is allocated for Legendre tables
Sieving with generic logic for p >= 3
Sieve started: 3 < p < 1e10 with 15000 terms (2501 < n < 10000, k*822^n+1) (expecting 14284 factors)
Must use generic sieving logic because abs(c) != 1 for at least one sequence
Sieving with generic logic for p >= 822
Split 2 base 822 sequences into 15 base 822^12 sequences.
Increasing worksize to 1024000 since each chunk is tested in less than a second
Increasing worksize to 4096000 since each chunk is tested in less than a second
Sieve completed at p=10000000033.
CPU time: 472.56 sec. (2.94 sieving) (13.53 cores)
1115 terms written to b822_n.abcd
Primes tested: 455052224. Factors found: 13885. Remaining terms: 1115. Time: 34.92 seconds.[/CODE]

Why is this different?

 storm5510 2023-05-03 17:00

[QUOTE=rebirther;629995]I have noticed that srsieve2 v1.7 is slower than 1.6.3 and have more remaining terms (this is a test only with 2 factors):

[CODE]g:\>srsieve2 -n2501 -N10000 -P1e10 -W16 -spl_remain.txt
srsieve2 v1.7, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Must use generic sieving logic because -l was not specified for mutiple sequences
Sieving with generic logic for p >= 3
Sieve started: 3 < p < 1e10 with 15000 terms (2501 < n < 10000, k*822^n+1) (expecting 14284 factors)
Sieving with generic logic for p >= 822
Split 2 base 822 sequences into 15 base 822^12 sequences.
Increasing worksize to 2000000 since each chunk is tested in less than a second
Sieve completed at p=10000000033.
CPU time: 741.56 sec. (3.00 sieving) (14.81 cores)
1152 terms written to b822_n.abcd
Primes tested: 455052224. Factors found: [B]13848[/B]. Remaining terms: 1152. Time: 50.08 seconds.[/CODE]

[CODE]g:\>srsieve2 -n2501 -N10000 -P1e10 -W16 -spl_remain.txt
srsieve2 v1.6.3, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Will use generic sieving logic because no memory is allocated for Legendre tables
Sieving with generic logic for p >= 3
Sieve started: 3 < p < 1e10 with 15000 terms (2501 < n < 10000, k*822^n+1) (expecting 14284 factors)
Must use generic sieving logic because abs(c) != 1 for at least one sequence
Sieving with generic logic for p >= 822
Split 2 base 822 sequences into 15 base 822^12 sequences.
Increasing worksize to 1024000 since each chunk is tested in less than a second
Increasing worksize to 4096000 since each chunk is tested in less than a second
Sieve completed at p=10000000033.
CPU time: 472.56 sec. (2.94 sieving) (13.53 cores)
1115 terms written to b822_n.abcd
Primes tested: 455052224. Factors found: [B]13885[/B]. Remaining terms: 1115. Time: 34.92 seconds.[/CODE]

Why is this different?[/QUOTE]

Look at the difference between "factors found."

 rebirther 2023-05-03 17:14

[QUOTE=storm5510;630002]Look at the difference between "factors found."[/QUOTE]

yeah but should be the same, in changelog there was:

[QUOTE]srsieve2/srsieve2cl: version 1.6.8
Fix issue where a single abs(c)=1 sequence finds an invalid factor. This
is caused by code that an unnecessary cast of a 32-bit value to a 16-bit value[/QUOTE]

If 1.6.3 is also affected should we are worried about?

 storm5510 2023-05-03 17:29

[QUOTE=rebirther;630003]yeah but should be the same...:

If 1.6.3 is also affected should we are worried about?[/QUOTE]

I feel it should be the same. What [B]rogue[/B] did to v1.6.8 would not be retroactive to an older version, like v1.6.3.

I tend to stay away from new releases for a while. I use v1.6.8 on a Win10 system. It is stable and does the job.

 rogue 2023-05-03 18:24

[QUOTE=rebirther;630003]yeah but should be the same, in changelog there was:

If 1.6.3 is also affected should we are worried about?[/QUOTE]

This same bug could cause it to miss factors. I only became aware of it because of the invalid factor.

 rogue 2023-05-08 23:28

I was playing around with srsieve2cl with an input file that has nearly 12,000 sequences. The default best q chosen was 3, but upon trying various q, I found out that q = 12 changes the rate from about 19k p/sec to 32k p/sec. Here are some of the estimated work efforts for q:

[code]
q = 1 with 11953 subseq yields bs = 25001, gs = 2, work = 53689
q = 2 with 23755 subseq yields bs = 25001, gs = 1, work = 58259
q = 4 with 33162 subseq yields bs = 12501, gs = 1, work = 58931
q = 3 with 23898 subseq yields bs = 16668, gs = 1, work = 50127
q = 6 with 35976 subseq yields bs = 8334, gs = 1, work = 58705
q = 12 with 46661 subseq yields bs = 4168, gs = 1, work = 69502
[/code]

The next best q is 6, but that topped out at about 23k p/sec.

All of the sequences chosen actually had best q of 48 and are combined into a single file. That q was worse than the others I tried.

So if you are going to spend days or weeks sieving a group of sequences, I suggest you play around with the q to determine which one is best.

You are probably wondering if the formula for computing the work effort is correct. It computes an estimate. I have tried playing with it to give more weight to some values more than others, but I could not find one that yields better results. The formula it currently uses is this:

[code]
#define BABY_WORK 1.0 // 1 mulmod, 1 insert
#define GIANT_WORK 1.0 // 1 mulmod, 1 lookup
#define EXP_WORK 0.7 // 1 mulmod
#define SUBSEQ_WORK 1.4 // 1 mulmod, 1 lookup (giant step 0)

double GenericSequenceHelper::EstimateWork(uint32_t Q, uint32_t s)
{
uint32_t babySteps, giantSteps;
double work;

ChooseSteps(Q, s, babySteps, giantSteps);

work = babySteps*BABY_WORK + s*(giantSteps-1)*GIANT_WORK + Q*EXP_WORK + s*SUBSEQ_WORK;
[/code]

This implies that BABY_WORK, EXP_WORK, or SUBSEQ_WORK are too high. If anyone wants to play around with this to come up with a better cost for each _WORK value, go for it.

 pepi37 2023-05-13 08:55

srsieve2 write
p=3354416722099,[B][COLOR="Red"] 4.174M p/sec[/COLOR][/B]

p/sec mean primes/sec or something else?

 rogue 2023-05-14 00:02

[QUOTE=pepi37;630606]srsieve2 write
p=3354416722099,[B][COLOR="Red"] 4.174M p/sec[/COLOR][/B]

p/sec mean primes/sec or something else?[/QUOTE]

Correct. Srsieve/sr1sieve/sr2sieve count range of p, not p. The correct way to compare is to run the same range of p thru both programs to determine which is faster.

 Citrix 2023-05-14 02:47

[QUOTE=rogue;630646]Correct. Srsieve/sr1sieve/sr2sieve count range of p, not p. The correct way to compare is to run the same range of p thru both programs to determine which is faster.[/QUOTE]

Does this mean a range of: x to x+4.174M is being done every second?
If this is case, maybe it should be changed to 4.174M/sec (or k/sec) to avoid confusion.

 pepi37 2023-05-14 10:02

[QUOTE=Citrix;630648]Does this mean a range of: x to x+4.174M is being done every second?
If this is case, maybe it should be changed to 4.174M/sec (or k/sec) to avoid confusion.[/QUOTE]
Not M, it show primes/ sec
That is totaly different value

 rogue 2023-05-14 19:40

[QUOTE=Citrix;630648]Does this mean a range of: x to x+4.174M is being done every second?
If this is case, maybe it should be changed to 4.174M/sec (or k/sec) to avoid confusion.[/QUOTE]

Everything built on the mtsieve framework counts the number of primes that have been used to look for factors. M in this case is "million".

Think of it this way, if p of 3, 5, 7, 11, 13, 17, and 19 are tested in a second, then it would output 7 p/sec. With srsieve/sr1sieve/sr2sieve, it would output 17 p/sec (19 - 3 + 1).

 rogue 2023-05-16 17:00

The next release of srsieve2/srsieve2cl will have better support for (k*b^n+c)/d sequences.

srsieve2/srsieve2cl only looks for factors of k*b^n+c, so there is special logic for handling d > 1.

If p divides k*b^n+c and d > p and gcd(p, d) > 0, then it will not treat p as a factor as there is no easy way to verify that if p divides (k*b^n+c) that it also divides (k*b^n+c)/d.

I added a new -r flag. This will remove terms for the sequence where (k*b^n+c) mod d != 0. Not using -r will be fine, but note that pfgw will floor((k*b^n+c)/d) before doing a PRP test.

 rogue 2023-05-18 14:13

I have updated the dev build of srsieve2/srsieve2cl 1.7 at sourceforge in case anyone wants to play around with it.

 storm5510 2023-05-18 17:55

[QUOTE=rogue;630873]I have updated the dev build of srsieve2/srsieve2cl 1.7 at sourceforge in case anyone wants to play around with it.[/QUOTE]

I gave it a try with 55 sequences of a job I am running for Gary. It drops out to the prompt during or after building the Legendre tables. The first time, I gave it 160MB to work with. The next, I gave it 256MB. It didn't seem to make any difference. Without the table parameter, it seem to run alright.

[CODE]srsieve2 v1.7, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
(kp) Sequence has algebraic factorization: 8000*190^n-1 -> (20^3)*190^n-1
(kp) Sequence 8000*190^n-1 has 25000 terms removed due to algebraic factors of the form 20*190^(n/3)-1
Sieving with generic logic for p >= 3
Sieve started: 3 < p < 1e10 with 4100055 terms (25000 < n < 100000, k*190^n-1) (expecting 3904433 factors)
Sieving with multi-sequence c=1 logic for p >= 57420
BASE_MULTIPLE = 2, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720
Split 55 base 190 sequences into 597 base 190^20 sequences.
Building Legendre tables: 4.1% done ETC 2023-05-18 13:48 (currently at k=16028)
Building Legendre tables: 8.2% done ETC 2023-05-18 13:49 (currently at k=22157)
Building Legendre tables: 12.2% done ETC 2023-05-18 13:49 (currently at k=29082)
Building Legendre tables: 16.3% done ETC 2023-05-18 13:49 (currently at k=30506)
Building Legendre tables: 20.4% done ETC 2023-05-18 13:49 (currently at k=31559)
Building Legendre tables: 24.5% done ETC 2023-05-18 13:49 (currently at k=33918)
Building Legendre tables: 28.6% done ETC 2023-05-18 13:49 (currently at k=37266)
Building Legendre tables: 32.7% done ETC 2023-05-18 13:49 (currently at k=39623)
Building Legendre tables: 36.7% done ETC 2023-05-18 13:49 (currently at k=42002)
Building Legendre tables: 40.8% done ETC 2023-05-18 13:49 (currently at k=44916)
Building Legendre tables: 44.9% done ETC 2023-05-18 13:49 (currently at k=45122)
[/CODE]

 rogue 2023-05-18 18:12

[QUOTE=storm5510;630890]I gave it a try with 55 sequences of a job I am running for Gary. It drops out to the prompt during or after building the Legendre tables. The first time, I gave it 160MB to work with. The next, I gave it 256MB. It didn't seem to make any difference. Without the table parameter, it seem to run alright.[/CODE][/QUOTE]

Can you post the file of sequences and the command line parameters for the different runs?

 storm5510 2023-05-18 22:12

1 Attachment(s)
[QUOTE=rogue;630891]Can you post the file of sequences and the command line parameters for the different runs?[/QUOTE]

Attached. The only difference between the two runs was [C]-l160M[/C] and [C]-l256M[/C].

55 was just a random slide of a mouse down a list of 554.

[I]srsieve2cl v1.7[/I] runs quite well.

 rogue 2023-05-19 16:47

[QUOTE=storm5510;630903]Attached. The only difference between the two runs was [C]-l160M[/C] and [C]-l256M[/C].

55 was just a random slide of a mouse down a list of 554.

[I]srsieve2cl v1.7[/I] runs quite well.[/QUOTE]

This is the result of a bug in how Legendre tables are built when there are multiple sequences. I have narrowed down the cause.

 storm5510 2023-05-20 00:15

[QUOTE=rogue;630924]This is the result of a bug in how Legendre tables are built when there are multiple sequences. I have narrowed down the cause.[/QUOTE]

Very good!

Is there a way to [U]stop[/U] [I]srsieve2[/I] from using Legendre tables for small groups of sequences, or just one? Sometimes, removing the [C]-l[/C] switch does not work. Why? Sometimes the tables will increase the throughput, and other times it slows it down.

 rogue 2023-05-20 03:23

[QUOTE=storm5510;630944]Very good!

Is there a way to [U]stop[/U] [I]srsieve2[/I] from using Legendre tables for small groups of sequences, or just one? Sometimes, removing the [C]-l[/C] switch does not work. Why? Sometimes the tables will increase the throughput, and other times it slows it down.[/QUOTE]

Don't use -l if you don't want Legendre tables for multiple sequences.

You have to use -l0 if you don't want Legendre tables for a single sequence.

 japelprime 2023-05-23 20:51

I have been running srsieve2cl for a test in Win command prompt. I can run the program through cpu but not on gpu.
I have reinstall OpenCL in different ways without success. I get always same output error. I am using Nvidia 760 gpu card. Reference to developer link page (in last http line) is probably outdated and the notes seems not there to be found.

>srsieve2cl.exe -i 1964_minus_47_ABC.txt -P 11e15 -o 1964_minus_48_ABC.txt -q 12 -l 256 -L Generic_sieve_logic -W 50 -g 128 -H -O Outputfaktor

OpenCL Error: Unknown
in call to clGetPlatformIDs
Please (re)install OpenCL as described at
//developer.amd.com/gpu/ATIStreamSDK/assets/ATI_Stream_SDK_Installation_Notes.pdf

 rogue 2023-05-23 21:24

[QUOTE=japelprime;631134]I have been running srsieve2cl for a test in Win command prompt. I can run the program through cpu but not on gpu.
I have reinstall OpenCL in different ways without success. I get always same output error. I am using Nvidia 760 gpu card. Reference to developer link page (in last http line) is probably outdated and the notes seems not there to be found.

>srsieve2cl.exe -i 1964_minus_47_ABC.txt -P 11e15 -o 1964_minus_48_ABC.txt -q 12 -l 256 -L Generic_sieve_logic -W 50 -g 128 -H -O Outputfaktor

OpenCL Error: Unknown
in call to clGetPlatformIDs
Please (re)install OpenCL as described at
//developer.amd.com/gpu/ATIStreamSDK/assets/ATI_Stream_SDK_Installation_Notes.pdf[/QUOTE]

Are the correct drivers installed? You likely need OpenCL 2.0 support.

 rogue 2023-05-24 13:46

I have posted mtsieve 2.4.7 to sourceforge. Here is a summary of the changes.

[code]
framework:
Added command line switch -4. Sieving will stop when the factors per
second rate falls below the specified rate. The rates only only evaluated
when the factor rate is computed, which is once per minute.

Added command line switch -5. Sieving will stop when the seconds per
factor rate falls is above specified rate. The rates only only evaluated
when the factor rate is computed, which is once per minute.

fbncsieve: version 1.6.2:
If max p is overridden due to the ability to factor out all composite terms,
then all remaining prime terms will be written the the output file as opposed
to some being written to the <xx>_primes.txt file.

gcwsieve/gcwsievecl: version 1.5.2
Modify output format to gcw_gfn.txt and gcw_mersenne.txt to make more sense.

srsieve2/srsieve2cl: version 1.7
Can now support hundreds of thousands of sequences per execution.

Added command line switch -S to split the sequences into separate files by
best Q for tha sequence. The resulting files should then be run with -q to
ensure that it uses the best Q for that set of sequences.

The software only factors k*b^n+/-c, even if d > 1. When d > 1 a couple
of other checks are in play.

When sieving sequences (k*b^n+/-c)/d where d > 1, terms where d > factor and
gcd(d, factor) > 0 will be not be removed when (k*b^n+/-c) mod factor = 0
because there is no easy way to verify that if factor divides (k*b^n+/-c)
that it also divides (k*b^n+/-c)/d.

Added command line switch -r for use with (k*b^n+/-c)/d sequences where d > 1.
When specified this will remove terms where k*b^n+/-c mod d != 0. If you do not
use -r then pfgw will use floor((k*b^n+/-c)/d) before doing the PRP test.
[/code]

Please let me know if you run into any issues.

 storm5510 2023-05-25 17:14

Something I stumbled upon: If I take an ABCD file created with a v1.6.x version of [I]srsieve2[/I], v1.7 will drop out to the command prompt after displaying, "Split x base x sequences into x base x^y sequences." If I start a new series with v1.7, then there is no problem continuing with an ABCD.

This is easily avoidable if a person is aware of it. I was not until now.

 rogue 2023-05-25 17:44

[QUOTE=storm5510;631245]Something I stumbled upon: If I take an ABCD file created with a v1.6.x version of [I]srsieve2[/I], v1.7 will drop out to the command prompt after displaying, "Split x base x sequences into x base x^y sequences." If I start a new series with v1.7, then there is no problem continuing with an ABCD.

This is easily avoidable if a person is aware of it. I was not until now.[/QUOTE]

Hmm. Post the ABCD file and I will take a look.

 ryanp 2023-05-26 01:51

Is the SVN repo at HEAD missing a file?

[CODE]\$ make -j 8 xyyxsieve
g++ -Isieve -m64 -Wall -DUSE_X86 -std=c++11 -O3 -c -o core/App_cpu.o core/App.cpp
g++ -Isieve -m64 -Wall -DUSE_X86 -std=c++11 -O3 -c -o core/FactorApp_cpu.o core/FactorApp.cpp
g++ -Isieve -m64 -Wall -DUSE_X86 -std=c++11 -O3 -c -o core/AlgebraicFactorApp_cpu.o core/AlgebraicFactorApp.cpp
g++ -Isieve -m64 -Wall -DUSE_X86 -std=c++11 -O3 -c -o core/Clock_cpu.o core/Clock.cpp
g++ -Isieve -m64 -Wall -DUSE_X86 -std=c++11 -O3 -c -o core/Parser_cpu.o core/Parser.cpp
g++ -Isieve -m64 -Wall -DUSE_X86 -std=c++11 -O3 -c -o core/Worker_cpu.o core/Worker.cpp
g++ -Isieve -m64 -Wall -DUSE_X86 -std=c++11 -O3 -c -o core/main_cpu.o core/main.cpp
g++ -Isieve -m64 -Wall -DUSE_X86 -std=c++11 -O3 -c -o core/SharedMemoryItem_cpu.o core/SharedMemoryItem.cpp
g++ -Isieve -m64 -Wall -DUSE_X86 -std=c++11 -O3 -c -o core/HashTable_cpu.o core/HashTable.cpp
make: *** No rule to make target 'core/BigHashTable_cpu.o', needed by 'xyyxsieve'. Stop.
make: *** Waiting for unfinished jobs....[/CODE]

 ryanp 2023-05-26 02:02

1 Attachment(s)
I'm also seeing a segfault with an existing build of [C]xyyxsievecl[/C]:

[CODE]\$ ./xyyxsievecl -i ./cand.txt -o newterms.txt -P 1e11 -G 16 -g 16 -M 1000000
xyyxsieve v1.8.1, a program to find factors numbers of the form x^y+y^x or x^y-y^x
Segmentation fault (core dumped)[/CODE]

cand.txt is attached. I debugged only a little; seems to be something to do with how it allocates the [C]iv_Terms[/C] array. It segfaults on the line assigning to it:

[CODE] if (haveBitMap)
{
iv_Terms[BIT(x, y)] = true; // array seems too small here.
il_TermCount++;
}[/CODE]

 rogue 2023-05-26 12:30

I committed the missing source file.

I will take a look at the segfault today.

Thanks for posting the file. I expect it to be an easy fix, but one never knows...

 storm5510 2023-05-26 15:08

2 Attachment(s)
[QUOTE=rogue;631247]Hmm. Post the ABCD file and I will take a look.[/QUOTE]

Attached are two ABCD files. One ran with v1.6.9 and the other with v1.7. Both are derived from a 60% test I did for R60: 11652*60^n-1. They are identical. I took the one from v1.6.9 and attempted a continuation with v1.70 and it accepted it.

So, some instances, it works and other times not. The best solution is to not cross from one to the other.

 rogue 2023-05-26 15:30

[QUOTE=rogue;631284]I committed the missing source file.

I will take a look at the segfault today.

Thanks for posting the file. I expect it to be an easy fix, but one never knows...[/QUOTE]

The root cause is that your range of x and y are too large and there isn't enough memory for the vector.

Although I have a solution, I don't like it because it negatively impacts performance. I need to spend more time on it.

 ryanp 2023-05-26 15:50

[QUOTE=rogue;631290]The root cause is that your range of x and y are too large and there isn't enough memory for the vector.[/QUOTE]

Ah OK. Presumably I could just split the file into several and then sieve each one separately?

 rogue 2023-05-26 16:57

[QUOTE=ryanp;631291]Ah OK. Presumably I could just split the file into several and then sieve each one separately?[/QUOTE]

In this case yes because most of the performance improvements come from overlapping ranges of y for each x and y for each y.

Now that I think about it I could probably modify it to be more "brute force" depending upon the sparseness of x and y. That shouldn't hurt performance and might even help it.

 storm5510 2023-05-28 23:08

The issue I mentioned with v1.7 of [I]srsieve2[/I] seems to continue. I can create a new sieve by using the [C]-s[/C] switch in the proper form. If I use that output as in input using [C]-i[/C] to elevate the levels of P, then it will drop out to the prompt. I should be able to work up a sample, if you would like.

[U]Edit[/U]: This happens on the [U]Riesel[/U] side only.

This will run properly:

[CODE]srsieve2 -n100e3 -N250e3 -p3 -P1e9 -W7 -r -s"2444*45^n[B]+[/B]1" -o1e9.abcd
srsieve2 -p1e9 -P5e9 -W7 -r -i1e9.abcd -o5e9.abcd[/CODE]

This will not:

[CODE]srsieve2 -n3 -N100e3 -p3 -P1e9 -W7 -s"22*173^n[B]-[/B]1" -o1e9.abcd
[/CODE]

I will stick with v1.6.9 for now.

 rogue 2023-05-30 15:09

[QUOTE=ryanp;631267]I'm also seeing a segfault with an existing build of [C]xyyxsievecl[/C]:

[CODE]\$ ./xyyxsievecl -i ./cand.txt -o newterms.txt -P 1e11 -G 16 -g 16 -M 1000000
xyyxsieve v1.8.1, a program to find factors numbers of the form x^y+y^x or x^y-y^x
Segmentation fault (core dumped)[/CODE]

[/QUOTE]

I have committed a code change and an update to the makefile. So if you are interesting in "giving it a spin", please do so. I think it should be faster than the version you are using now. The main difference is that since the range of x and y exceed the number of actual candidates, it will store the list of candidates differently and iterate thru them differently. Unfortunately there is no great way to optimize the sieving based upon the input.

 rogue 2023-05-30 15:43

[QUOTE=storm5510;631442]The issue I mentioned with v1.7 of [I]srsieve2[/I] seems to continue. I can create a new sieve by using the [C]-s[/C] switch in the proper form. If I use that output as in input using [C]-i[/C] to elevate the levels of P, then it will drop out to the prompt. I should be able to work up a sample, if you would like.

[U]Edit[/U]: This happens on the [U]Riesel[/U] side only.

This will run properly:

[CODE]srsieve2 -n100e3 -N250e3 -p3 -P1e9 -W7 -r -s"2444*45^n[B]+[/B]1" -o1e9.abcd
srsieve2 -p1e9 -P5e9 -W7 -r -i1e9.abcd -o5e9.abcd[/CODE]

This will not:

[CODE]srsieve2 -n3 -N100e3 -p3 -P1e9 -W7 -s"22*173^n[B]-[/B]1" -o1e9.abcd
[/CODE]

I will stick with v1.6.9 for now.[/QUOTE]

I cannot reproduce this. Did you use the version in the mtsieve 2.4.7 or the stand-alone one?

[code]
srsieve2 -n3 -N100e3 -p3 -P1e9 -W7 -s"22*173^n-1" -o1e9.abcd
srsieve2 v1.7, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Sieving with generic logic for p >= 3
Sieve started: 3 < p < 1e9 with 99998 terms (3 <= n <= 100000, k*173^n-1) (expecting 94697 factors)
Sieving with single sequence c=1 logic for p >= 257
BASE_MULTIPLE = 30, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720
Split 1 base 173 sequence into 15 base 173^60 sequences.
Legendre summary: Approximately 952 bytes needed for Legendre tables
... removed ...
Increasing worksize to 2000000 since each chunk is tested in less than a second
Sieve completed at p=1026219533.
CPU time: 48.14 sec. (0.47 sieving) (4.84 cores)
3384 terms written to 1e9.abcd
Primes tested: 50847327. Factors found: 96614. Remaining terms: 3384. Time: 9.95 seconds.

srsieve2 -n3 -N100e3 -p3 -P1e9 -W7 -s"22*173^n+1" -o1e9.abcd
srsieve2 v1.7, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Sieving with generic logic for p >= 3
Sieve started: 3 < p < 1e9 with 99998 terms (3 <= n <= 100000, k*173^n+1) (expecting 94697 factors)
Sieving with single sequence c=1 logic for p >= 257
BASE_MULTIPLE = 30, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720
Split 1 base 173 sequence into 27 base 173^60 sequences.
Legendre summary: Approximately 6 bytes needed for Legendre tables
... removed ...
Increasing worksize to 2000000 since each chunk is tested in less than a second
Sieve completed at p=1000000007.
CPU time: 57.88 sec. (0.48 sieving) (4.91 cores)
7644 terms written to 1e9.abcd
Primes tested: 50847326. Factors found: 92354. Remaining terms: 7644. Time: 11.79 seconds.
[/code]

 storm5510 2023-05-30 16:33

[QUOTE=rogue;631531]I cannot reproduce this. Did you use the version in the mtsieve 2.4.7 or the stand-alone one?
[/QUOTE]

It is the one packaged with the [I]srbsieve[/I] archive with an internal date of 5/24/2023. The one within [I]mtsieve 2.4.7[/I] has an internal date of 4/13/2023. I look at these with the file properties. Extracting them changes the visible date stamp in the file explorer. I honestly can't say if I ever tried the latter.

 rogue 2023-05-30 17:03

There is mtsieve_2.4.6.7z and mtsieve_2.4.7.7z. 2.4.7 is the latest and is the one I ran without an issue.

 storm5510 2023-05-30 22:45

[QUOTE=rogue;631538]There is mtsieve_2.4.6.7z and mtsieve_2.4.7.7z. 2.4.7 is the latest and is the one I ran without an issue.[/QUOTE]

Now, I cannot reproduce it.

The one I mentioned from April is v1.6.9, so scrap that one.

An [I]srbsieve_1.3[/I] archive containing 21 files and [I]mtsieve v2.4.7[/I] both have [I]srsieve2[/I] in them. The date stamps are one day apart even though the file lengths are the same.

I think I will just wait and see if this happens again.

 rogue 2023-05-31 00:05

[QUOTE=storm5510;631551]Now, I cannot reproduce it.

The one I mentioned from April is v1.6.9, so scrap that one.

An [I]srbsieve_1.3[/I] archive containing 21 files and [I]mtsieve v2.4.7[/I] both have [I]srsieve2[/I] in them. The date stamps are one day apart even though the file lengths are the same.

I think I will just wait and see if this happens again.[/QUOTE]

I removed the standalone one. I released separately because it wasn't fully ready.

 storm5510 2023-05-31 14:01

[QUOTE=rogue;631553]I removed the standalone one. I released separately because it wasn't fully ready.[/QUOTE]

The standalone? You mean the one in the [I]mtsieve[/I] package?

I started a new sieve yesterday evening. I have been using the v1.7 from the [I]srbsieve_1.3[/I] archive. No problems whatsoever.

 rogue 2023-05-31 15:45

[QUOTE=storm5510;631580]The standalone? You mean the one in the [I]mtsieve[/I] package?

I started a new sieve yesterday evening. I have been using the v1.7 from the [I]srbsieve_1.3[/I] archive. No problems whatsoever.[/QUOTE]

That srsieve2 is current. If I included in the srbsieve package, then I made a mistake.

 rogue 2023-06-01 18:21

mtsieve 2.4.8 is released. Here are the changes:

[code]
fbncsieve: version 1.7
No longer remove even k for base 2.
Ensure that odd bases only report even k that are removed.
Ignore factors for terms where k is outside of specified range.

xyyxsieve/xyyxsievecl: version 2.0
If the range of x or the range of y is greater than the number of candidates,
then different logic is used to manage the candidates and iterate over them.
[/code]

Various bugs where reported with fbncsieve 1.6.x. Don't use that version.

 pepi37 2023-06-02 23:28

Can you write ( inside mtsieve package) small program that will show is alg factors in specific sequence ( that user choose) and write small report like number of alg factors?
That can be used for confirming there is no alg factors left in seqeunce

 pepi37 2023-06-03 07:13

srsieve2 ( from last package 2.4.8)
If I try to apply factors I got error

Fatal Error: Invalid factor: 16*767^504684+1 mod 10994911890479476681 = 8563234858453284832
Fatal Error: Invalid factor: 4*767^500350+1 mod 18446744073709551615 = 2

Factor are confirmed
(16*767^504684+1)%10994911890479476681 is Zero (0)
(4*767^500350+1)%367677432715278443521 is Zero (0)

 henryzz 2023-06-03 11:45

[QUOTE=pepi37;631734]srsieve2 ( from last package 2.4.8)
If I try to apply factors I got error

Fatal Error: Invalid factor: 16*767^504684+1 mod 10994911890479476681 = 8563234858453284832
Fatal Error: Invalid factor: 4*767^500350+1 mod 18446744073709551615 = 2

Factor are confirmed
(16*767^504684+1)%10994911890479476681 is Zero (0)
(4*767^500350+1)%367677432715278443521 is Zero (0)[/QUOTE]

I suspect it isn't designed to check factors more than 64 bits large.

 rogue 2023-06-03 12:29

[QUOTE=henryzz;631738]I suspect it isn't designed to check factors more than 64 bits large.[/QUOTE]

That is correct.

 ryanp 2023-06-05 11:47

FYI, latest SVN build of [C]srsieve2[/C] segfaults on some fairly reasonable looking inputs.

[CODE]\$ ./srsieve2 -s "7*2^n-1" -P 1e13 -n 8e6 -N 20e6 -W 36 -o out.txt
srsieve2 v1.7, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Sieving with generic logic for p >= 3
Sieve started: 3 <= p <= 1e13 with 12000001 terms (8000000 <= n <= 20000000, k*2^n-1) (expecting 11559581 factors)
Sieving with single sequence c=1 logic for p >= 257
BASE_MULTIPLE = 30, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720
Split 1 base 2 sequence into 23 base 2^180 sequences.
Legendre summary: Approximately 4 bytes needed for Legendre tables
1 total sequences
1 are eligible for Legendre tables
0 are not eligible for Legendre tables
0 have Legendre tables in memory
1 cannot have Legendre tables in memory
0 have Legendre tables loaded from files
0 required building of the Legendre tables
518400 bytes used for congruent q and ladder indices
259200 bytes used for congruent qs and ladders
Segmentation fault[/CODE]

 rogue 2023-06-05 12:04

[QUOTE=ryanp;631824]FYI, latest SVN build of [C]srsieve2[/C] segfaults on some fairly reasonable looking inputs.

[CODE]\$ ./srsieve2 -s "7*2^n-1" -P 1e13 -n 8e6 -N 20e6 -W 36 -o out.txt
srsieve2 v1.7, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Sieving with generic logic for p >= 3
Sieve started: 3 <= p <= 1e13 with 12000001 terms (8000000 <= n <= 20000000, k*2^n-1) (expecting 11559581 factors)
Sieving with single sequence c=1 logic for p >= 257
BASE_MULTIPLE = 30, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720
Split 1 base 2 sequence into 23 base 2^180 sequences.
Legendre summary: Approximately 4 bytes needed for Legendre tables
1 total sequences
1 are eligible for Legendre tables
0 are not eligible for Legendre tables
0 have Legendre tables in memory
1 cannot have Legendre tables in memory
0 have Legendre tables loaded from files
0 required building of the Legendre tables
518400 bytes used for congruent q and ladder indices
259200 bytes used for congruent qs and ladders
Segmentation fault[/CODE][/QUOTE]

Thanks for the bug report. I will take a look.

 rogue 2023-06-05 14:30

I found a bug when it generated Legendre tables for single sequences. I fixed that and pushed the code change.

But I ran into another issue. I have a work-around, but I suspect another bug that I need to dig into.

 rogue 2023-06-07 13:39

mtsieve 2.4.9 is released. Here are the changes:

[code]
framework:
Added command line switch -6. When the removal rate is computed as "seconds
per factor", this is the number of minutes to includes in that rate. It can
exceed that number of minutes, but only if no factors are found.

fnbcsieve: version 1.7.1
For base 2 do not adjust mink or maxk when they are even. End user can use -r
to remove those terms.

srsieve2/srsieve2cl: version 1.7.1
Fix two issues with generating Legendre tables that can cause program to crash.
Fix issue where some sequences are removed due to incorrect algebraic factorizations.
[/code]

I also added on FUTURE item:

[code]
Add feature to compute rate for the last xx factors instead of seconds per factor.
[/code]

With the two changes I have not been able to reproduce the srsieve2 crash. It should fix the single sequence and multi-sequence Legendre table creation issues.

 ryanp 2023-06-10 19:08

I'm also seeing [C]xyyxsievecl[/C] hang on inputs like this:

[CODE]\$ ./xyyxsievecl -s "-" -x 3 -X 16 -y 1e6 -Y 1200e3 -g 16 -G 16 -P 1e8 -o xyyx_minus.txt
xyyxsieve v2.0, a program to find factors numbers of the form x^y+y^x or x^y-y^x
Quick elimination of terms info (in order of check):
0 because x >= y
1400007 because the term is even
265357 because x and y have a common divisor[/CODE]

At this point, it seems to just be stuck. I've left it open for hours and it's not apparently doing anything. This is on a machine with an NVIDIA A100...

 pepi37 2023-06-10 21:54

I do some more experiment with srsieve2cl to find fastest way for sieving single sequence. Regardless fact it is "simple fact" i will ask to confirm

[QUOTE]GPU primes per worker is [B][COLOR="Red"]85411840[/COLOR][/B]
Sieve started: 10000680668335321 < p < 15e15 with 8480 terms (2250390 <= n <= 2999886, k*53^n+1) (expecting 92 factors)
p=10002326398611403, [COLOR="Red"][B]10.08M p/sec[/B][/COLOR], no factors found, 0.0% done.[/QUOTE]

Will more primes per worker result as faster sieving speed?

 Happy5214 2023-06-15 12:54

All of the non-OpenCL executable directives in the Makefile include [c]\$(LD_FLAGS_OPENCL)[/c], which fails on computers without OpenCL.

 rogue 2023-06-15 14:16

[QUOTE=Happy5214;632400]All of the non-OpenCL executable directives in the Makefile include [c]\$(LD_FLAGS_OPENCL)[/c], which fails on computers without OpenCL.[/QUOTE]

Did you use "make cpu_all" or just "make"? Use "make cpu_all" if you have no OpenCL.

 Happy5214 2023-06-16 20:53

[QUOTE=rogue;632403]Did you use "make cpu_all" or just "make"? Use "make cpu_all" if you have no OpenCL.[/QUOTE]

I only needed one program, so I used "make srsieve2". It compiled, but failed to link (specifically mentioning [c]-lOpenCL[/c]).

Line 386 of the Makefile (the rule for srsieve2) is:
[code]\$(CC) \$(CPP_FLAGS) \$(OPT_CPP_FLAGS) [b]\$(LD_FLAGS_OPENCL)[/b] -o \$@ \$^ \$(LD_FLAGS)[/code]

 rogue 2023-06-16 21:19

[QUOTE=Happy5214;632475]I only needed one program, so I used "make srsieve2". It compiled, but failed to link (specifically mentioning [c]-lOpenCL[/c]).

Line 386 of the Makefile (the rule for srsieve2) is:
[code]\$(CC) \$(CPP_FLAGS) \$(OPT_CPP_FLAGS) [b]\$(LD_FLAGS_OPENCL)[/b] -o \$@ \$^ \$(LD_FLAGS)[/code][/QUOTE]

I see. I have committed a change to the makefile. See if that resolves this issue.

 Citrix 2023-06-16 22:16

A bug with twinsieve. The program does not abort if all terms have been sieved.

[CODE]
twinsieve.exe -W16 -k2 -K7000 -n7000 -b2 -p3 -P10e14 -fA -t1
twinsieve v1.6.1, a program to find factors of k*b^n+1/-1 numbers for fixed b and n and variable k
Sieve started: 3 <= p <= 1e15 with 3499 terms (3 < k < 6999, k*2^7000) (expecting 3388 factors)
Increasing worksize to 10000000 since each chunk is tested in less than a second
Increasing worksize to 50000000 since each chunk is tested in less than a second
p=43401596201, 38.24M p/sec, 3499 factors found at 51.62 f/sec (last 1 min), 0.0% done. ETC 2023-07-02 23:35
Decreasing worksize to 25000000 since each chunk needs more than 5 seconds to test
...

[/CODE]

 rogue 2023-06-16 22:26

[QUOTE=Citrix;632483]A bug with twinsieve. The program does not abort if all terms have been sieved.

[CODE]
twinsieve.exe -W16 -k2 -K7000 -n7000 -b2 -p3 -P10e14 -fA -t1
twinsieve v1.6.1, a program to find factors of k*b^n+1/-1 numbers for fixed b and n and variable k
Sieve started: 3 <= p <= 1e15 with 3499 terms (3 < k < 6999, k*2^7000) (expecting 3388 factors)
Increasing worksize to 10000000 since each chunk is tested in less than a second
Increasing worksize to 50000000 since each chunk is tested in less than a second
p=43401596201, 38.24M p/sec, 3499 factors found at 51.62 f/sec (last 1 min), 0.0% done. ETC 2023-07-02 23:35
Decreasing worksize to 25000000 since each chunk needs more than 5 seconds to test
...

[/CODE][/QUOTE]

I don't think it has a check for that. I will have to take a look.

 Citrix 2023-06-16 22:30

I don't think the twinsieve 1.6.1 in the latest release is working correctly. For n=7001 it produces the following which has small factors (3 and 11)

[CODE]
ABC \$a*2^7001+1 & \$a*2^7001-1 // Sieved to 41213171663
4879

[/CODE]

 pepi37 2023-06-17 07:52

As always if I take new CRUS reservation, and that reservation has no sieve file I run it with srsieve2. When pass some level I switch to srsieve2cl and run it on GPU so I can free CPU to testing. Afer that I do some very light P-1 on mprime so I remove some extra factors.
Last two times using [B][I][U][COLOR="Red"]latest srsieve2 build[/COLOR][/U][/I][/B] regardless fact I sieve to [B][COLOR="Red"]2e13 [/COLOR][/B] I found with P-1 that some factors are not found with srsieve2 or better to say factors are missed..
So that is not big deal, but on the other side, I dont know how many of them are missed.
I like srsieve2 since it run MT and very nice use all cores so efficiency is very high but to be prepared some factors can be missed.

For S773 missed factors found by P-1 was

2*773^466005+1 has a factor: 4153116809
2*773^353085+1 has a factor: 71389978241
2*773^428381+1 has a factor: 396476137649
2*773^457997+1 has a factor: 411344474899

Every one here can confirm or deny my statement, run that sequence from 350K to 500K with srsieve2.
If it is my error then I apologize to Rogue, but I think srsieve2 miss some factors.

 gd_barnes 2023-06-17 09:42

[QUOTE=pepi37;632493]As always if I take new CRUS reservation, and that reservation has no sieve file I run it with srsieve2. When pass some level I switch to srsieve2cl and run it on GPU so I can free CPU to testing. Afer that I do some very light P-1 on mprime so I remove some extra factors.
Last two times using [B][I][U][COLOR="Red"]latest srsieve2 build[/COLOR][/U][/I][/B] regardless fact I sieve to [B][COLOR="Red"]2e13 [/COLOR][/B] I found with P-1 that some factors are not found with srsieve2 or better to say factors are missed..
So that is not big deal, but on the other side, I dont know how many of them are missed.
I like srsieve2 since it run MT and very nice use all cores so efficiency is very high but to be prepared some factors can be missed.

For S773 missed factors found by P-1 was

2*773^466005+1 has a factor: 4153116809
2*773^353085+1 has a factor: 71389978241
2*773^428381+1 has a factor: 396476137649
2*773^457997+1 has a factor: 411344474899

Every one here can confirm or deny my statement, run that sequence from 350K to 500K with srsieve2.
If it is my error then I apologize to Rogue, but I think srsieve2 miss some factors.[/QUOTE]

Were the factors missed in srsieve2 or srsieve2cl ?

 pepi37 2023-06-17 13:14

[QUOTE=gd_barnes;632497]Were the factors missed in srsieve2 or srsieve2cl ?[/QUOTE]

First two, small ones, 100% with srsieve2.

 gd_barnes 2023-06-17 18:14

[QUOTE=pepi37;632505]First two, small ones, 100% with srsieve2.[/QUOTE]

Can you post the exact command that you ran? I will see if I can duplicate the problem.

We need to know the following:
1. How many cores were you running?
2. Were you using Legendre tables?
3. Were you running specifically -s "2*773^n+1" stand-alone or with the multiple k's remaining on base S773?
4. Confirming since you stated you were running the latest srsieve2: Were you running version 1.7.1?

 Happy5214 2023-06-17 18:37

[QUOTE=gd_barnes;632513]Can you post the exact command that you ran? I will see if I can duplicate the problem.

We need to know the following:
1. How many cores were you running?
2. Were you using Legendre tables?
3. Were you running specifically -s "2*773^n+1" stand-alone or with the multiple k's remaining on base S773?
4. Confirming since you stated you were running the latest srsieve2: Were you running version 1.7.1?[/QUOTE]

This is all useful information to determine the exact parameters.

My testing with Legendre tables, 3 cores, [c]-s "2*773^n+1"[/c] and non-GPU version 1.7.1 directly built (on Linux) from SVN 294 could not reproduce it (i.e. it found all 4 factors listed, and specifically had 634 remaining at 5e11), but different parameters may result in a bug.

 gd_barnes 2023-06-17 19:25

I ran the following command on only 1 core to P=1e11:
srsieve2 -P100e9 -n350e3 -N500e3 -W1 -O factors.txt -s "2*773^n+1"

With only 1 sequence, srsieve2 will default to using Legendre tables, which it did here.

It found 149,333 factors leaving 668 remaining including the first two in your post.

I then ran old srsieve/sr1sieve for the same and had them output all factors. The factor and final sieve files both matched the srsieve2 run.

So...no luck duplicating the problem there.

I'm now running srsieve2 on 2 cores with all 5 k's remaining for base S773. I had to tell it to use Legendre tables with the -l switch since there was more than one sequence. I'll post results when done.

 gd_barnes 2023-06-17 21:06

The problem occurs when running more than one sequence with Legendre tables. It's definitely missing factors.

I have experienced this before and thought it was something I was doing wrong.

I ran this command:
srsieve2 -P100e9 -n350e3 -N500e3 -W2 -l10e3 -O factors.txt -s input-S773.txt

Where input-S773.txt contains the 5 sequences for CRUS base S773.

It did not find the first two factors that Pepi mentioned and appears to miss many more than that.

I then ran the above command without the -l switch. It has reached P=10e9 already and quickly found the 1st factor that Pepi mentioned. It will continue to P=100e9 to attempt to find the second factor that he listed.

I haven't checked if it would have the problem running only 1 core.

I don't have time to post many details right now. I'll post a detailed analysis of the situation in the morning.

My current suggestion: Don't run srsieve2 with the Legendre tables on more than one sequence.

 storm5510 2023-06-17 21:54

[QUOTE=gd_barnes;632523]...My current suggestion: Don't run srsieve2 with the Legendre tables on more than one sequence.[/QUOTE]

I am using Legendre tables on my R78 sieve, but it is srsieve2 v1.6.9. It was the same with R60. Using them increases the "p/sec" value by 40% with these two bases.

Using [C]-l0[/C] will disable the default for single sequences.

If this issue effected v1.6.9 and I have to start over, then I will need to rethink my position. As it is, it will take until late September to reach P=35e12. The alternate is 5000 seconds/factor and above. This is with using the tables.

 pepi37 2023-06-17 23:11

So Gary give me idea: I used fully sieved file and sieve it again from 3 to 72509819519 ( that was point when I switch to srsieve2cl.)
This time I didnot use legendre tables [B]and srsieve2 found 4 missed factor[/B]s.

[CODE]1311997931 | 2*773^391941+1
4153116809 | 2*773^466005+1
13039318073 | 2*773^373701+1
71389978241 | 2*773^353085+1[/CODE]

I will continue sieving to the morning to see will I find any more missed factor. I didnot expect that since I switch to srsieve2cl and since srsiev2cl doesnot support legendre tables I doubt will find any new missed factors.
But until I test I will not know truth..

 pepi37 2023-06-18 07:43

Found 4 more factors at sieve depth of 2448363815561. Testing is finished.

[CODE]284218780297 | 2*773^433277+1
362156606827 | 2*773^377117+1
396476137649 | 2*773^428381+1
411344474899 | 2*773^457997+1[/CODE]

And rogue if it is possible please allow that srsieve2 can remove factors more than 64 bits large. If sr.exe can remove it, and that is old program
I dont see reason why srsieve2 as newer and much better program cannot do that...

 gd_barnes 2023-06-18 09:52

srsieve2 missing factors with Legendre tables

2 Attachment(s)
Srsieve2 is missing a significant number of factors when running more than one sequence with the Legendre tables.

I'm running on Windows 10 the latest srsieve2 version 1.7.1. 6 cores are running in the background on other prime search stuff on an 8-core/8-thread I7-9700 machine.

I ran the following two commands on 2 cores:

Run #1 with Legendre tables:
srsieve2 -P100e9 -n350e3 -N500e3 -l10e3 -W2 -O factors.txt -s input-S773.txt

Run #2 without Legendre tables:
srsieve2 -P100e9 -n350e3 -N500e3 -W2 -O factors.txt -s input-S773.txt

The input-S773.txt file contains the remaining sequences for CRUS base S773 as follows:
[code]
2*773^n+1
8*773^n+1
10*773^n+1
16*773^n+1
32*773^n+1
[/code]

Attachment 1:
The no-Legendre run #2 found 138 factors that were not found by the Legendre run #1! 61 factors (44%) were < 100,000. The smallest factor missed was 3037. Run #2 also found factor 4937 four times specifically for 4 n's of the sequence 2*773^n+1 that were missed in run #1.

All of the factors < 1e11 that Pepi had found missed are on the list.

Attachment 2:
Of the above 138 factors missed, run #1 found 95 higher factors for the same sequences where it had missed smaller factors that it should have found.

So in total, 138 - 95 = 43 sequences were left in the sieve that should not have been.

Run #3 old srsieve/sr2sieve process:
For verification, I ran the old-school srsieve/sr2sieve process before any algebraic factors code was introduced. After manually removing algebraic factors for a couple of the sequences, it matched the no-Legendre run #1.

Synopsis of remaining terms in the sieve files:
Run #1 with tables: 7705 terms
Run #2 without tables: 7662 terms
Run #3 old-school: 7662 terms

So we are good if we avoid the use of Legendre tables when running more than one sequence.

This issue has probably existed ever since Legendre tables were introduced into srsieve2 because I noticed it over a year ago. Unfortunately I didn't know enough about the program at the time to know if I was running it correctly. Now I/we know that it has a problem.

Storm, don't rerun or start over on anything. If some factors are missed, it just means a little bit of extra primality testing for us in the future. If it was removing factors that it should not, that would be very bad.

Mainly this is a problem to be aware of going forward. People should decide on their own whether they want to run srsieve2 at a slower speed, run it with the Legendre tables for a somewhat less accurate run, or run multiple instances of sr2sieve and mess with having to manually remove factors.

Personally I will stick with using no Legendre tables when running srsieve2.

Pepi, if you sieved all 5 sequences on the base, you could use attachment #1 here to maybe remove more factors for P<1e11.

Mark, hopefully this is enough detail to look more into the problem.

 pepi37 2023-06-18 10:26

Found 4 more factors that are removed :)

So all is OK with srsieve2 if legendre tables are not used? That is very nice info.
Then I will stick with 1.7.1 dont use legendre tables and have nice sieving :)
Thanks Gary.

For rouge: maybe is best thing to do , and make temporary fix until you find solution to remove " - l " switch from command line and release 1.7,2 version

 gd_barnes 2023-06-18 11:41

[QUOTE=pepi37;632544]Found 4 more factors that are removed :)

So all is OK with srsieve2 if legendre tables are not used? That is very nice info.
Then I will stick with 1.7.1 dont use legendre tables and have nice sieving :)
Thanks Gary.

For rouge: maybe is best thing to do , and make temporary fix until you find solution to remove " - l " switch from command line and release 1.7,2 version[/QUOTE]

I'm glad you were able to knock out some more factors there.

One more note: I ran my Run #1 from my last post with Legendre tables again but this time on only 1 core. Same results.

The number of cores that it is run on makes no difference.

 rogue 2023-06-18 13:06

Regarding the srsieve2 issue with missing factors, is this only when using Legendre tables? Does this happen only when sieving multiple sequences or does it also happen when sieving a single sequence?

 gd_barnes 2023-06-18 13:17

2 Attachment(s)
I took another look at this and decided to do a run with and without Legendre tables running on only 1 core. This time I only ran it to P=1e9.

What this did is make the factor files a lot cleaner. Running on multiple cores, if more than one factor is found for a sequence at nearly the same moment on multiple cores, often it won't write out the smallest factor among them. This makes comparing factor files from two runs of 2 cores each more difficult.

When running on only one core, it was much easier to isolate what is going on when comparing what was found from the Legendre and no-Legendre runs.

Run #1 same as before on only 1 core to P=1e9 with Legendre tables:
srsieve2 -P1e9 -n350e3 -N500e3 -l10e3 -W1 -O factors.txt -s input-S773.txt

Run #2 same as before on only 1 core to P=1e9 without Legendre tables:
srsieve2 -P1e9 -n350e3 -N500e3 -W1 -O factors.txt -s input-S773.txt

Run 1 found 660,572 factors, 9432 terms remain.
Run 2 found 660,616 factors, 9388 terms remain.

A difference of 44 factors.

Run 1 contained 24 factors not found in run 2. (attachment 1)
Run 2 contained 68 factors not found in run 1. (attachment 2)
68 - 24 = 44

All terms with factors found in run 1 had the same terms with smaller factors in run 2. So run 2 (without Legendre tables) was not technically missing any factors.

Like before, the runs contained k = 2, 8, 10, 16, & 32 from base S773.

New information:

All of the missing factors are from k=2 (!) Yet k = 10 is a much higher-weight k than any of the others.

This was discerned due to removing the "noise" of different factors being found from multiple cores.

So maybe this will help isolate the problem. Could it be only the smallest k within a group of k's that is losing factors when Legendre tables are used?

 gd_barnes 2023-06-18 13:20

[QUOTE=rogue;632554]Regarding the srsieve2 issue with missing factors, is this only when using Legendre tables? Does this happen only when sieving multiple sequences or does it also happen when sieving a single sequence?[/QUOTE]

Not on one sequence. Only on multiple sequences.

Only with Legendre tables.

Number of cores doesn't matter.

Per my latest run in the last post, it only missed factors on the lowest k out of 5 k's. I don't know if that would always be the case.

 Happy5214 2023-06-18 13:54

Is it worth testing different Legendre table sizes, or would all table sizes have this issue?

 storm5510 2023-06-18 14:34

[QUOTE=gd_barnes;632542]...Storm, don't rerun or start over on anything. If some factors are missed, it just means a little bit of extra primality testing for us in the future. If it was removing factors that it should not, that would be very bad.

Mainly this is a problem to be aware of going forward. People should decide on their own whether they want to run srsieve2 at a slower speed, run it with the Legendre tables for a somewhat less accurate run, or run multiple instances of sr2sieve and mess with having to manually remove factors.

Personally, I will stick with using no Legendre tables when running srsieve2.[/QUOTE]

Very well. I will push on.

I will remove the Legendre flags from my command line. I had only been using them for a short time so, hopefully, very little was missed, if any.

 rogue 2023-06-18 16:02

Which version of srsieve2? I fixed an issue with Legendre tables in 1.7.1.

 pepi37 2023-06-18 16:07

Can you commit change on Sourceforge so I can compile new version?

Happy5214 you are right... I was thinking about, but write wrong... :)

 Happy5214 2023-06-18 16:18

[QUOTE=pepi37;632568]Can you commit change on github so I can compile new version?

To be clear, the source code is on Sourceforge (in a Subversion repo), not on GitHub. If you're getting it from GitHub, your code is likely out-of-date.

 rogue 2023-06-18 16:36

[QUOTE=pepi37;632568]Can you commit change on Sourceforge so I can compile new version?

Happy5214 you are right... I was thinking about, but write wrong... :)[/QUOTE]

Which change are you referring to?

 pepi37 2023-06-18 16:42

[QUOTE=rogue;632573]Which change are you referring to?[/QUOTE]

I was refer to your today post
Which version of srsieve2? I fixed an issue with Legendre tables in 1.7.1.

 Happy5214 2023-06-18 18:36

[QUOTE=pepi37;632576]I was refer to your today post
Which version of srsieve2? I fixed an issue with Legendre tables in 1.7.1.[/QUOTE]

I believe they're SVN revisions 291 through 293, which have already been posted. However, reading the previous posts, those fixes were for outright crashes, not missed factors.

 rogue 2023-06-18 18:51

[QUOTE=Happy5214;632580]I believe they're SVN revisions 291 through 293, which have already been posted. However, reading the previous posts, those fixes were for outright crashes, not missed factors.[/QUOTE]

That is misleading. The Legendre logic could trigger a crash, but it didn't always do so. It is possible that when it didn't crash that it would miss factors.

 gd_barnes 2023-06-18 19:50

[QUOTE=rogue;632567]Which version of srsieve2? I fixed an issue with Legendre tables in 1.7.1.[/QUOTE]

It is the latest 1.7.1 on SourceForge.

This problem has existed for a very long time. When I first noticed it over a year ago, I did not know much about the program and thought I was doing something wrong.

I know you are busy but please look at all of my posts in detail. I can see that you have not viewed the attachments, which would give you good information about what is going on.

All of the questions that you are asking me were already answered. All of my posts describe exactly the tests that I ran and the exact missing factors. Doing that will save you a lot of time in the long run.

 rogue 2023-06-19 01:40

[QUOTE=gd_barnes;632589]It is the latest 1.7.1 on SourceForge.

This problem has existed for a very long time. When I first noticed it over a year ago, I did not know much about the program and thought I was doing something wrong.

I know you are busy but please look at all of my posts in detail. I can see that you have not viewed the attachments, which would give you good information about what is going on.

All of the questions that you are asking me were already answered. All of my posts describe exactly the tests that I ran and the exact missing factors. Doing that will save you a lot of time in the long run.[/QUOTE]

There are a number of posts and piecing together bits and pieces across them is tedious.

I will take a look at what is happening with Legendre table logic for multiple sequences as soon as I have the opportunity.

 gd_barnes 2023-06-19 07:16

[QUOTE=rogue;632610]There are a number of posts and piecing together bits and pieces across them is tedious.

I will take a look at what is happening with Legendre table logic for multiple sequences as soon as I have the opportunity.[/QUOTE]

So info. about the specific factors that were missed, how the tests were run, and the narrowing down of the circumstances that are creating the problem is tedious to look through?

I know I'm long-winded but I thought that would be info. you would need to see to isolate a problem that's existed for an extended period. Anyway I hope the info. can eventually help you narrow it down.

 rogue 2023-06-19 13:41

[QUOTE=Citrix;632485]I don't think the twinsieve 1.6.1 in the latest release is working correctly. For n=7001 it produces the following which has small factors (3 and 11)

[CODE]
ABC \$a*2^7001+1 & \$a*2^7001-1 // Sieved to 41213171663
4879

[/CODE][/QUOTE]

I cannot reproduce this. What range of k did you use?

 Citrix 2023-06-19 22:25

[code]
twinsieve.exe -W1 -k2 -K7001 -n7001 -b2 -p3 -P1e11 -fA -t1
twinsieve v1.6.1, a program to find factors of k*b^n+1/-1 numbers for fixed b and n and variable k
Sieve started: 3 <= p <= 1e11 with 3500 terms (3 < k < 7001, k*2^7001) (expecting 3348 factors)
Increasing worksize to 1600000 since each chunk is tested in less than a second
Increasing worksize to 40000000 since each chunk is tested in less than a second
p=35243280493, 25.13M p/sec, 3499 factors found at 84.38 f/sec (last 1 min), 35.2% done. ETC 2023-06-19 17:25
p=69548741681, 23.96M p/sec, 3499 factors found at 53.02 f/sec (last 2 min), 69.5% done. ETC 2023-06-19 17:25

[/code]

 gd_barnes 2023-06-19 22:53

[QUOTE=Citrix;632655][code]
twinsieve.exe -W1 -k2 -K7001 -n7001 -b2 -p3 -P1e11 -fA -t1
twinsieve v1.6.1, a program to find factors of k*b^n+1/-1 numbers for fixed b and n and variable k
Sieve started: 3 <= p <= 1e11 with 3500 terms (3 < k < 7001, k*2^7001) (expecting 3348 factors)
Increasing worksize to 1600000 since each chunk is tested in less than a second
Increasing worksize to 40000000 since each chunk is tested in less than a second
p=35243280493, 25.13M p/sec, 3499 factors found at 84.38 f/sec (last 1 min), 35.2% done. ETC 2023-06-19 17:25
p=69548741681, 23.96M p/sec, 3499 factors found at 53.02 f/sec (last 2 min), 69.5% done. ETC 2023-06-19 17:25

[/code][/QUOTE]

It is down to the final term remaining. I suspect it may have something to do with not wanting to remove that final term.

To confirm this, you could expand the k range to -k2 -K100000. If that term no longer shows, then that is the problem.

To confirm it further, you could even test a narrower k-range such as 2 to 4000. If this is the problem, you should end up with a different single term remaining since the original one was k>4000.

 Citrix 2023-06-19 23:03

[QUOTE=gd_barnes;632658]It is down to the final term remaining. I suspect it may have something to do with not wanting to remove that final term.

To confirm this, you could expand the k range to -k2 -K100000. If that term no longer shows, then that is the problem.

To confirm it further, you could even test a narrower k-range such as 2 to 4000. If this is the problem, you should end up with a different single term remaining since the original one was k>4000.[/QUOTE]

The problem is it is removing numbers that are not composites and leaving the composites in the output file.
4879*2^7001+-1 is the term remaining which has small factors.

I believe this bug is introduced in latest version-with the even k values removed for base 2. The program is still finding factors for even k value.
[CODE]
3 | 4810*2^7001+1
3 | 4816*2^7001+1
3 | 4822*2^7001+1
3 | 4828*2^7001+1
3 | 4852*2^7001+1
3 | 4858*2^7001+1
3 | 4870*2^7001+1
3 | 4876*2^7001+1
3 | 4888*2^7001+1
[/CODE]

 rogue 2023-06-19 23:52

I know what the problem is now with twin sieve. I will fix.

 rogue 2023-06-20 18:21

I have committed the change for twinsieve. Regarding srsieve2 I have been able to reproduce the issue in a reliable way that will make it easier for me to debug. sr2sieve finds the factors, but srsieve2 does not (when using Legendre tables). I do not know how long it will take me to find the issue and fix it.

In doing this test one thing I did not expect was that srsieve2 would be 30x faster than sr2sieve for these five sequences of S777. I'm sure some of that is because sr2sieve was built without the asm code and with -O2. srsieve2 was built with -O3, but has no asm either. This is probably not true for higher p, but I have no explanation why srsieve2 is that much faster. In other comparison tests I have run sr2sieve was faster than srsieve2.

 ryanp 2023-06-22 03:42

xyyxsievecl behavior

I'm doing some simple tests with [C]xyyxsievecl[/C], and would like to understand the output:

[CODE]\$ ./xyyxsievecl -g 16 -G 16 -P 1e10 -x 300e3 -X 301e3 -y 150e3 -Y 151e3 -s '+' -o out.txt -M 1e6
xyyxsieve v2.0, a program to find factors numbers of the form x^y+y^x or x^y-y^x
Quick elimination of terms info (in order of check):
0 because y >= x
501001 because the term is even
95143 because x and y have a common divisor
GPU primes per worker is 442368
Sieve started: 3 <= p <= 1e10 with 405857 terms (300000 <= x <= 301000, 150000 <= y <= 151000) (expecting 386492 factors)
p=0, 0.000 p/sec, 97708 factors found at 342.2 f/sec (last 1 min)
p=0, 0.000 p/sec, 102860 factors found at 91.61 f/sec (last 2 min)
p=0, 0.000 p/sec, 195274 factors found at 100.6 f/sec (last 3 min)
p=0, 0.000 p/sec, 284963 factors found at 101.6 f/sec (last 4 min)
p=20952199, 4.358K p/sec, 376301 factors found at 89.79 f/sec (last 5 min)
p=6462271, 7.261K p/sec, 384344 factors found at 70.84 f/sec (last 6 min
p=6462271, 15.55K p/sec, 384620 factors found at 59.50 f/sec (last 7 min)
p=36131591, 19.96K p/sec, 384992 factors found at 54.15 f/sec (last 8 min), 0.3% done. ETC 2023-06-23 17:00
p=51694691, 22.58K p/sec, 385334 factors found at 44.99 f/sec (last 9 min)
p=51694691, 26.85K p/sec, 385643 factors found at 40.45 f/sec (last 10 min), 0.5% done. ETC 2023-06-23 12:16 [/CODE]

Why does [C]p[/C] stay at 0 for a while, then suddenly jump up, drop back down, etc (and occasionally remain stuck for a while at the same value)? Is this expected behavior, something to do with GPU threading, or a legitimate bug?

(Note: this is on an A100 GPU, and the overall speed isn't remotely close to what I'd expect.)

 kruoli 2023-06-22 11:49

Yes, it seems like it has to do with threading. Usually, you should not start a sieve from fresh with the ...cl variants, instead start with the non-cl variants up to p=1e9 (for example) and then let the ...cl variant take over.

[STRIKE]You should set -G to 108 (number of SMs).[/STRIKE] You should set -g to 108 (number of SMs) and leave out -G for a beginning.

Edit: Setting -M to such a large number is usually a sign you did something not intended. You should be able to leave it out when doing it the way I described above.

All times are UTC. The time now is 00:13.