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.