mtsieve

[rogue]

Originally Posted by Happy5214

I assume that's both an algorithmic and processor unit advantage (Montgomery arithmetic with integers on the faster ALU vs. a more straightforward implementation with floats on the slower FPU, or whatever unit handles SSE). I compiled a few of the Montgomery functions to ASM on x86 just to see how much optimization GCC does on them with -O2, and at least on REDC and mul I couldn't find anywhere to hand-optimize. I imagine ARM would be similar, though I'd have to get my ODROID set up again (we switched to a new ISP and that messed up the wiring setup) to know for sure.

If you want to do some comparisons on your own, take a look at the MpArith.h class and it uses. MpArithVec.h is the same, but does 4 at a time. I expect -O2/-O3 to help greatly when using that.

[rogue]

In making changes to sgsieve to work like the Sophie-Germain sieve in newpgen, it appears that newpgen is missing factors for 2p+1 terms. sgsieve is outputting valid factors (per pfgw). I need to do more investigation to see if I am misunderstanding something else.

[rogue]

I think that I have determined what is happening.

sgsieve is sieving for k*b^n-1 and 2*k*b^n-1

I suspect that newpgen is sieving for k*b^n-1 and k*b^(n+1)-1

sgsieve is sieving for the traditional form which is p and 2p+1. This is only a problem when b != 2.

I do not know if anyone is sieving for b != 2 with newpgen.

I do not know if llr, pfgw, sgsieve, and newpgen are all in sync with npg file formats when b != 2.

I would appreciate if someone could run some tests with llr, pfgw, and newpgen to determine if they all handle the npg file format for Sophie-Germains properly for b != 2.

[rogue]

I looked again at the pfgw doc on newpgen formats. I was correct. When the base != 2, then newpgen sieves per my suspicion. I will modify sgsieve to support a switch for "true" SG sieving (what it does now) or "generalized" SG sieving (which is what newpgen does). Since nobody (as far as I know) is searching for Sophie-Germain primes for base != 2, this shouldn't be a problem.

Note this is one of the reasons I dislike newpgen file formats. ABC and ABCD formats are easier to understand.

[twobombs]

Originally Posted by rogue

In making changes to sgsieve to work like the Sophie-Germain sieve in newpgen, it appears that newpgen is missing factors for 2p+1 terms. sgsieve is outputting valid factors (per pfgw). I need to do more investigation to see if I am misunderstanding something else.

FYI: mtsieve runs into compile errors on the Sophie-Germain code since a couple of days. ( see attachment of Docker Hub build log)

Code invoking the build : https://github.com/twobombs/theremin...file-sieve#L12

[rogue]

Originally Posted by twobombs

FYI: mtsieve runs into compile errors on the Sophie-Germain code since a couple of days. ( see attachment of Docker Hub build log)

Code invoking the build : https://github.com/twobombs/theremin...file-sieve#L12

Which compiler is this? The syntax is correct. [] is an overloaded operator of MpResVector.

Does mfsieve build? It uses the same syntax.

[japelprime]

I was looking at fkbncsieve. In the html multi- threaded sieve framework link it says this program is for both k*b^n+1 and k*b^n-1 form. Using Command prompt and fbncsieve -h it says k*b^n+c form. Is there any -1 or +1 switch for fbncsieve win batch file for some of the mtsieve programs. I was just thinking of start sieving k*b^n-1 from scratch without any "-i" input file and also later with input file.

C:\EB\Prime\mtsieve\mtsieve_2.3.2 - profa>fkbnsieve -h
fkbnsieve v1.4, a program to find factors of k*b^n+c numbers for fixed k, b, and n and variable c
-h --help prints this help
-p --pmin=P0 sieve start: P0 < p (default 1)
-P --pmax=P1 sieve end: p < P1 (default 2^62)
-w --worksize=w primes per chunk of work (default 1000000)
-W --workers=W start W workers (default 0)
-A --applyandexit apply factors and exit (used with -I)
-i --inputterms=i input file of remaining candidates
-I --inputfactors=I input file with factors (used with -A)
-o --outputterms=o output file of remaining candidates
-O --outputfactors=O output file with new factors
-c --cmin=c Minimum c to search
-C --cmax=C Maximum c to search
-s --sequence=s Sequence to find factors of in form k*b^n+c where k, b, and n are integer values

[rogue]

Originally Posted by japelprime

I was looking at fkbncsieve. In the html multi- threaded sieve framework link it says this program is for both k*b^n+1 and k*b^n-1 form. Using Command prompt and fbncsieve -h it says k*b^n+c form. Is there any -1 or +1 switch for fbncsieve win batch file for some of the mtsieve programs. I was just thinking of start sieving k*b^n-1 from scratch without any "-i" input file and also later with input file.

C:\EB\Prime\mtsieve\mtsieve_2.3.2 - profa>fkbnsieve -h
fkbnsieve v1.4, a program to find factors of k*b^n+c numbers for fixed k, b, and n and variable c
-h --help prints this help
-p --pmin=P0 sieve start: P0 < p (default 1)
-P --pmax=P1 sieve end: p < P1 (default 2^62)
-w --worksize=w primes per chunk of work (default 1000000)
-W --workers=W start W workers (default 0)
-A --applyandexit apply factors and exit (used with -I)
-i --inputterms=i input file of remaining candidates
-I --inputfactors=I input file with factors (used with -A)
-o --outputterms=o output file of remaining candidates
-O --outputfactors=O output file with new factors
-c --cmin=c Minimum c to search
-C --cmax=C Maximum c to search
-s --sequence=s Sequence to find factors of in form k*b^n+c where k, b, and n are integer values

Not certain that I understand your question. You can use -1 or +1 for "+c".

[japelprime]

Originally Posted by rogue

Not certain that I understand your question. You can use -1 or +1 for "+c".

Of course. Silly me.
Thanks.

[rogue]

I have finally released mtsieve 2.3.3. Changes include:

   framework:
      Updated primesieve to 7.9.  This addresses an issue in primesieve that can crash
      the mtsieve applications.
      
      Changed usage of primesieve (thanks to hints from Kim Wallisch, its creator) to
      improve sieving peformance.  As a result the worker threads now use an array instead
      of a vector.
      
      Broke the main sieving loop into two loops, one for when limited to a single thread
      or for sieving prior to switching to the GPU.  The second loop handles multiple worker
      threads much better.
      
      Reduced the initial CPU worksize from 1e6 to 96e3.  When the largest prime tested
      reaches 1e6, the worker thread can automatically adjust the worksize in an effort
      to have each chunk take between 1 and 5 seconds to process.  This has two affects.
      First, it will allow the CPU workers to stop more quickly when the user hits ^C.
      Second, it will do a better job at keeping CPU workers busy when using mulitple workers.
 
   fkbnsieve: version 1.5
      Only verify the first few factors found for each prime to speed up initial sieve.

   sgsieve: version 1.3
      Changed to support p/2p+1 where p is of the form k*b^n-1.  This makes it compatible
      with newpgen.  As of 1.2 p was of the form k*b^n+1.

   srsieve2: vesion 1.6.3
      Default to not use Legendre tables for multiple sequences unless -l is used.

I have still not completed the Metal changes with testing. It has been a busy summer so I can't get that to the finish line. I think it is close.
I just need to have the time and motivation to finish. The sieves with no x86 ASM will compile on ARM and thus on Apple's M1/M2 CPUs.

[japelprime]

I notice trouble with the ^ sign for me in batch file. Maybe this error outcome is regarding my wrong format for k*b^n+c but I am not sure what is wrong when the output file is not the same as input.
command promt shows -s k*21964-1 (without powerfaktor ^) but my batch file is written with k*2^1964-1

Command prompt:
C:\EB\Prime\mtsieve\fbncsieve_minus_1964>fbncsieve.exe -s k*21964-1 -k 1 -K 4000000 -P 10e14 -o remaining_faktors_prufa.txt
fbncsieve v1.4, a program to find factors of k*b^n+c numbers for fixed b, n, and c and variable k
Fatal Error: sequence must be in form k*b^n+c where you specify values for b, n and c