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

2022-05-27, 05:03   #639
axn

Jun 2003

2×2,693 Posts

Quote:
 Originally Posted by dannyridel So in essence, both types of Cunningham Chains, if they result in prime pairs, can count as SG pairs? Eg. SG pairs can be either (p,2p-1) or (p,2p+1)?
No. Only (p, 2p+1) is SG

Quote:
 Originally Posted by rogue Sophie Germain: A prime p is said to be a Sophie Germain prime if both p and 2p+1 are prime.
When p=k*2^n-1, 2p+1 = k*2^(n+1)-1. Both are easily provable by LLR.
When p=k*2^n+1, 2p+1 = k*2^(n+1)+3, but is still provable, since, by definition, we have 100% factorization of N-1. But you'll need PFGW with p=k*2^n+1 as a helper

Last fiddled with by axn on 2022-05-27 at 05:07

 2022-05-27, 13:15 #640 rogue     "Mark" Apr 2003 Between here and the 1A1916 Posts From the pfgw doc on newpgen formats: Code: 99991:S:0:11:10 k*11^n-1 & k*11^(n+1)-1 (SG) (generalized SG since base is not 2) 99991:C:0:2:5 k*2^n+1 & k*2^(n+1)+1 (CC) 99991:B:0:2:15 k*2^n+-1 & k*2^(n+1)+-1 (BiTwin) 99991:Y:3:2:29 k*2^n+-1 & k*2^(n-1)+1 & k*2^(n+1)+1 (LP) 99991:Z:3:2:46 k*2^n+-1 & k*2^(n-1)-1 & k*2^(n+1)-1 (LM) 99991:J:3:2:11 k*2^n+-1 & k*2^(n+1)-1 (Twin/SG) 99991:K:3:2:7 k*2^n+-1 & k*2^(n+1)+1 (Twin/CC) 99991:1:3:2:42 CC 1st kind len 3 k*2^(n-1)-1 & k*2^n-1 & k*2^(n+1)-1 99991:2:3:2:21 CC 2st kind len 3 k*2^(n-1)+1 & k*2^n+1 & k*2^(n+1)+1 sgsieve is outputting the second type because it is using k*2^n+1 instead of k*2^n-1. The difference between "C", "1", and "2" is that "C" always has length of 2 whereas "1" and "2" will have a length > 2. Note that sgsieve is limited to base 2. It should allow for other bases. At some point I will modify sgsieve to be more generic. Some day I will create a ccsieve to support all of the forms above. sgsieve might be rolled into ccsieve when that happens. It appears that the pfgw doc has CC 1st kind and CC 2nd kind reversed per the definition of Cunningham Chains (see MathWorld), but it is possible that newpgen is also reversed. There are a few possible places with a mistake: the pfgw doc, the pfgw code, the llr code, the newpgen code. I suspect that all of them are wrong. It would be easy enough in the pfgw doc to change the description of "1" and "2", but that could be misleading if anyone is using newpgen.
 2022-05-29, 15:25 #641 Happy5214     "Alexander" Nov 2008 The Alamo City 11001110012 Posts Regarding the ARM version, what ever happened to the ARM ASM routines I sent you? Those were supposed to be translations of the fpu_*.S files for x86. Did those not work? Edit: They were attached to this post. Last fiddled with by Happy5214 on 2022-05-29 at 15:33 Reason: Found post
2022-05-30, 00:11   #642
rogue

"Mark"
Apr 2003
Between here and the

3×17×131 Posts

Quote:
 Originally Posted by Happy5214 Regarding the ARM version, what ever happened to the ARM ASM routines I sent you? Those were supposed to be translations of the fpu_*.S files for x86. Did those not work? Edit: They were attached to this post.
I have not integrated them yet. I suspect that the non-asm version of the mulmod is faster, but I have not compared the speeds. I only say that because the non-asm version is faster than the x86 asm. AVX is faster than the non-asm version of the mulmod, but very few of the sieves use AVX.

2022-06-02, 16:01   #643
dannyridel

"AMD YES!"
Jan 2020
Bellevue, WA

2·41 Posts

Quote:
 Originally Posted by rogue From the pfgw doc on newpgen formats: Code: 99991:S:0:11:10 k*11^n-1 & k*11^(n+1)-1 (SG) (generalized SG since base is not 2) 99991:C:0:2:5 k*2^n+1 & k*2^(n+1)+1 (CC) 99991:B:0:2:15 k*2^n+-1 & k*2^(n+1)+-1 (BiTwin) 99991:Y:3:2:29 k*2^n+-1 & k*2^(n-1)+1 & k*2^(n+1)+1 (LP) 99991:Z:3:2:46 k*2^n+-1 & k*2^(n-1)-1 & k*2^(n+1)-1 (LM) 99991:J:3:2:11 k*2^n+-1 & k*2^(n+1)-1 (Twin/SG) 99991:K:3:2:7 k*2^n+-1 & k*2^(n+1)+1 (Twin/CC) 99991:1:3:2:42 CC 1st kind len 3 k*2^(n-1)-1 & k*2^n-1 & k*2^(n+1)-1 99991:2:3:2:21 CC 2st kind len 3 k*2^(n-1)+1 & k*2^n+1 & k*2^(n+1)+1 sgsieve is outputting the second type because it is using k*2^n+1 instead of k*2^n-1. The difference between "C", "1", and "2" is that "C" always has length of 2 whereas "1" and "2" will have a length > 2. Note that sgsieve is limited to base 2. It should allow for other bases. At some point I will modify sgsieve to be more generic. Some day I will create a ccsieve to support all of the forms above. sgsieve might be rolled into ccsieve when that happens.
So this means that the files that sgsieve are outputting actually don't sieve for sg pairs but for CC chains of second kind?

I found a CC length 2 of 2nd kind with it anyways...

2022-06-02, 16:35   #644
rogue

"Mark"
Apr 2003
Between here and the

11010000110012 Posts

Quote:
 Originally Posted by dannyridel So this means that the files that sgsieve are outputting actually don't sieve for sg pairs but for CC chains of second kind? I found a CC length 2 of 2nd kind with it anyways...
Sorry I have created some confusion as I have confused myself. newpgen and pfgw are correct. My math was wrong.

If a term output from sgsieve is prime/PRP, then it is both Sophie-Germain and CC of the first kind, length 2.

I need to look at sgsieve and verify that it is doing what I think it is doing. I just haven't had time to do that.

If pfgw or llr say that both terms are prime/PRP, then that is good enough.

2022-06-03, 01:38   #645
dannyridel

"AMD YES!"
Jan 2020
Bellevue, WA

10100102 Posts

Quote:
 Originally Posted by rogue Sorry I have created some confusion as I have confused myself. newpgen and pfgw are correct. My math was wrong. If a term output from sgsieve is prime/PRP, then it is both Sophie-Germain and CC of the first kind, length 2. I need to look at sgsieve and verify that it is doing what I think it is doing. I just haven't had time to do that. If pfgw or llr say that both terms are prime/PRP, then that is good enough.

Oh that's fine. At least twinsieve works :)
LLR does find the primes, but they don't find SGs, as I said above.
When will the fix come out?

2022-06-03, 12:28   #646
rogue

"Mark"
Apr 2003
Between here and the

3·17·131 Posts

Quote:
 Originally Posted by dannyridel Oh that's fine. At least twinsieve works :) LLR does find the primes, but they don't find SGs, as I said above. When will the fix come out?
I do not know. I have yet to finish the work for the Apple Metal support. I'm close to getting that working, but I haven't had much time.

 2022-06-03, 16:02 #647 rogue     "Mark" Apr 2003 Between here and the 3×17×131 Posts I have just uploaded mtsieve 2.3.2 to sourceforge. Here are the changes: Code: Switched to llvm-mingw compiler in Windows. I have tried three other compilers, I cannot use gdb with the latest msys2 or mingw64 compilers. gdb gives an error when I start the programs, but only if they are built with -g. The latest cygwin compiler fails to link the code. Others have seen the same error I have seen with other sofwtware and nobody has provided a solution. There were some spurious reports of bugs with the 2.3.0/2.3.1 release. This bugs seem to have gone away now that I switched to llvm-mingw. framework: Updated primesieve to 7.8. All remaining SSE code has been removed due to a bug resetting the rounding mode. kbbsieve was the only program using it and is now faster without it. Created abstract Device and Kernel classes and extend OpenCL and Metal classes from those. This means that none of the GpuWorker classes need to include or need to rely on logic specific to OpenCL or Metal as the implementation is hidden from those workers. kbbsieve: version 1.1 Switched to Montgomery logic. This is about 20% faster than the SSE logic. The bug reported by ryanp still exists. This seems to be a problem when starting a new sieve with -W > 1. Unfortunately although gdb is now working again, I cannot reproduce when running within gdb. For the time being I suggest starting the sieve with a single worker and sieving to 1e4. Once sieved to that depth, start srsieve2 again using the output from the previous run and -W > 1. srsieve should automatically do that. In other words it should use only a single worker to start (to knock out all of the candidates with small divisors), then start the other workers. I suspect problem lies with that mechanism.
2022-06-03, 16:37   #648
rogue

"Mark"
Apr 2003
Between here and the

3×17×131 Posts

Quote:
 Originally Posted by rogue The bug reported by ryanp still exists. This seems to be a problem when starting a new sieve with -W > 1. Unfortunately although gdb is now working again, I cannot reproduce when running within gdb. For the time being I suggest starting the sieve with a single worker and sieving to 1e4. Once sieved to that depth, start srsieve2 again using the output from the previous run and -W > 1. srsieve should automatically do that. In other words it should use only a single worker to start (to knock out all of the candidates with small divisors), then start the other workers. I suspect problem lies with that mechanism.
Upon further review, this appears to be a bug in primesieve given the stack trace or that primesieve is triggering a bug on the OS. It does not consistently crash on Windows, which is why I'm having difficulty reproducing the problem. In other words I can sometimes run and it fails and I can sometimes run and it does not fail. I just cannot get it to fail under gdb. Very annoying. I will see if I can reproduce on OS X.

Last fiddled with by rogue on 2022-06-03 at 16:39

2022-06-06, 15:09   #649
Happy5214

"Alexander"
Nov 2008
The Alamo City

11001110012 Posts

Quote:
 Originally Posted by rogue I have not integrated them yet. I suspect that the non-asm version of the mulmod is faster, but I have not compared the speeds. I only say that because the non-asm version is faster than the x86 asm. AVX is faster than the non-asm version of the mulmod, but very few of the sieves use AVX.
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.

All times are UTC. The time now is 15:09.

Thu Aug 11 15:09:27 UTC 2022 up 35 days, 9:56, 3 users, load averages: 1.91, 1.63, 1.49