mtsieve

[henryzz]

Originally Posted by pepi37

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)

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

[rogue]

Originally Posted by henryzz

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

That is correct.

[ryanp]

FYI, latest SVN build of srsieve2 segfaults on some fairly reasonable looking inputs.

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

[rogue]

Originally Posted by ryanp

FYI, latest SVN build of srsieve2 segfaults on some fairly reasonable looking inputs.

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

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

[rogue]

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]

mtsieve 2.4.9 is released. Here are the changes:

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.

I also added on FUTURE item:

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

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]

I'm also seeing xyyxsievecl hang on inputs like this:

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

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]

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

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

Will more primes per worker result as faster sieving speed?

[Happy5214]

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

[rogue]

Originally Posted by Happy5214

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

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

[Happy5214]

Originally Posted by rogue

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

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

Line 386 of the Makefile (the rule for srsieve2) is:

$(CC) $(CPP_FLAGS) $(OPT_CPP_FLAGS) $(LD_FLAGS_OPENCL) -o $@ $^ $(LD_FLAGS)