mersenneforum.org mtsieve
 Register FAQ Search Today's Posts Mark Forums Read

2022-06-06, 15:39   #650
rogue

"Mark"
Apr 2003
Between here and the

3·5·443 Posts

Quote:
 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.

 2022-06-06, 16:10 #651 rogue     "Mark" Apr 2003 Between here and the 3×5×443 Posts 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.
 2022-06-07, 14:55 #652 rogue     "Mark" Apr 2003 Between here and the 3·5·443 Posts 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.
 2022-06-07, 18:38 #653 rogue     "Mark" Apr 2003 Between here and the 664510 Posts 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.
2022-06-08, 18:59   #654
twobombs

Jun 2022

2 Posts

Quote:
 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
Attached Thumbnails

2022-06-08, 19:36   #655
rogue

"Mark"
Apr 2003
Between here and the

3×5×443 Posts

Quote:
 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.

All times are UTC. The time now is 19:01.

Wed Jun 29 19:01:30 UTC 2022 up 76 days, 17:02, 0 users, load averages: 1.43, 1.38, 1.34