mtsieve

[rogue]

Originally Posted by Plutie

This is most likely an issue with my syntax, but when I run srsieve2 with a sequence in the form (k*b^n+c)/d, the program does not seem to be recognizing the division.

uwu@DESKTOP-7I8GNER:~/Math/mtsieve$ ./srsieve2 -W2 -o=45557 -s"(41*10^n+13)/9" -n100001 -N150000
srsieve2 v1.3.1, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Sieving with generic logic
Sieve started: 3 < p < 2^62 with 50000 terms (100001 < n < 150000, k*10^n+c)
Fatal Error:  Invalid factor: 41*10^100001+13 mod 3 = 12

There are some gaps in the factor validation for these. I'll take a look to see if I can fix them.

[rogue]

I have released 2.1.5. Here are the changes:

   framework:
      Added MpArith.h (non-vectorized) and changed class names in MpArithVector.h.
      Overloaded HashTable constructor as needed for srsieve2.
   
   srsieve2, srsieve2cl:  version 1.4
      Lots of refactoring to support special sieving logic for c=1 sequences.
      Implemented sr1sieve logic using Montgomery mulmod logic (CPU only).
      Change array of sequences to a linked list to avoid compiler warnings.
      Add support for pmin= line in input file (as generated by srsieve/srfile).

This is a beta release for srsieve2 and srsieve2cl because I had to refactor a lot of code in order to implement the c=1 logic (sr1sieve) cleanly. As this is a beta, I am asking interested users to give it a spin. You should be able to start sieving a new sequence and it will switch to the c=1 logic automatically.

Right now the c=1 logic only works for a single sequence. If you have multiple sequences it will use the generic logic. Support for multiple sequences will come in the future, but that isn't next on my list. The c=1 logic is about 15% slower than sr1sieve based upon the limited testing I have done. Most of that is due to having zero hand-tuned ASM in that logic. sr1sieve has a ton of ASM and I am rather loathe to pull it into srsieve2. On the plus side I intend to focus next on fixing bugs (if any are reported) and implementing the OpenCL logic for a single c=1 sequence. It should be doable, but I don't know how fast it will be or if I will find other limits that prevent it from performing well.

I think that the issue reported by Plutie is fixed, but I have not tested it.

[Dylan14]

Compiling the latest version of mtsieve (r92) fails at CisOneSequenceHelper.cpp:

g++ -Isieve -m64 -Wall -O3 -std=c++11 -c -o sierpinski_riesel/CisOneSequenceHelper_cpu.o sierpinski_riesel/CisOneSequenceHelper.cpp 
sierpinski_riesel/CisOneSequenceHelper.cpp:13:10: fatal error: HashTable.h: No such file or directory
   13 | #include "HashTable.h"
      |          ^~~~~~~~~~~~~
compilation terminated.
make: *** [makefile:131: sierpinski_riesel/CisOneSequenceHelper_cpu.o] Error 1

This is fixed if line 13 is changed to

#include "../core/HashTable.h"

[rogue]

Originally Posted by Dylan14

Compiling the latest version of mtsieve (r92) fails at CisOneSequenceHelper.cpp:

g++ -Isieve -m64 -Wall -O3 -std=c++11 -c -o sierpinski_riesel/CisOneSequenceHelper_cpu.o sierpinski_riesel/CisOneSequenceHelper.cpp 
sierpinski_riesel/CisOneSequenceHelper.cpp:13:10: fatal error: HashTable.h: No such file or directory
   13 | #include "HashTable.h"
      |          ^~~~~~~~~~~~~
compilation terminated.
make: *** [makefile:131: sierpinski_riesel/CisOneSequenceHelper_cpu.o] Error 1

This is fixed if line 13 is changed to

#include "../core/HashTable.h"

Thanks. I wonder why it compiles in Windows. In any case that #include is not needed.

BTW, if anyone has ideas for optimizations for the new c=1 logic, I would appreciate if you posted them in the "mtsieve enhancements" thread.

[pepi37]

srsieve2 -P 11000000000000000 -W4 -w 1e7 -i t16_b155_k4.npg -o t16_b155_k4.npg -f B -O factgenefer.txt

Last version crash, version 1.3 works without problems

[rogue]

Originally Posted by pepi37

Last version crash, version 1.3 works without problems

Can you post or e-mail me the input file?

[pepi37]

Originally Posted by rogue

Can you post or e-mail me the input file?

This is part of input file

10000000000000000:P:1:155:257
4 1174326
4 1174366
4 1174374
4 1174582
4 1174598
4 1174630
4 1174646
4 1174830
4 1174950
4 1174974
4 1174998
4 1175014
4 1175142
4 1175150
4 1175254
4 1175278
4 1175302
4 1175398
4 1175430
4 1175454
4 1175574
4 1175742
4 1175822

[rogue]

Found the problem. It will be fixed in the next release.

[pepi37]

Great news, thanks!

[rogue]

I posted 1.4.1 of srsieve2 at sourceforge in its own 7z file.

Upon some further testing, it is about 30% slower than sr1sieve (with x86 asm) and 10% slower than sr1sieve (with no x86 asm).

I fully expect that srsieve2cl with c=1 support in the GPU will be much faster than sr1sieve even on modest GPUs, so I'm not too concerned about the poorer performance at this time. As much as I would love to stop supporting sr1sieve, I don't think that is going to happen anytime soon.

[henryzz]

Originally Posted by rogue

I posted 1.4.1 of srsieve2 at sourceforge in its own 7z file.

Upon some further testing, it is about 30% slower than sr1sieve (with x86 asm) and 10% slower than sr1sieve (with no x86 asm).

I fully expect that srsieve2cl with c=1 support in the GPU will be much faster than sr1sieve even on modest GPUs, so I'm not too concerned about the poorer performance at this time. As much as I would love to stop supporting sr1sieve, I don't think that is going to happen anytime soon.

Is that comparison without sr1sieve using a Legendre symbol cache? As far as I can tell srsieve2 with sr1sieve logic is spending around 30% of its time calculating legendre symbols. I get the following message if I try to turn it on "Ingoring -L option since Legendre tables cannot be used"

Also I get a seg fault after running "./srsieve2 -P 1e9 -n 1 -N 100000 -s "19920911*2^n+1""

This is using r95 of the code on Sourceforge.