mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2022-05-27, 05:03   #639
axn
 
axn's Avatar
 
Jun 2003

2×2,693 Posts
Default

Quote:
Originally Posted by dannyridel View Post
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 View Post
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
axn is offline   Reply With Quote
Old 2022-05-27, 13:15   #640
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

1A1916 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2022-05-29, 15:25   #641
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

11001110012 Posts
Default

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
Happy5214 is offline   Reply With Quote
Old 2022-05-30, 00:11   #642
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3×17×131 Posts
Default

Quote:
Originally Posted by Happy5214 View Post
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.
rogue is offline   Reply With Quote
Old 2022-06-02, 16:01   #643
dannyridel
 
dannyridel's Avatar
 
"AMD YES!"
Jan 2020
Bellevue, WA

2·41 Posts
Default

Quote:
Originally Posted by rogue View Post
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...
dannyridel is offline   Reply With Quote
Old 2022-06-02, 16:35   #644
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

11010000110012 Posts
Default

Quote:
Originally Posted by dannyridel View Post
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.
rogue is offline   Reply With Quote
Old 2022-06-03, 01:38   #645
dannyridel
 
dannyridel's Avatar
 
"AMD YES!"
Jan 2020
Bellevue, WA

10100102 Posts
Default

Quote:
Originally Posted by rogue View Post
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?
dannyridel is offline   Reply With Quote
Old 2022-06-03, 12:28   #646
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·17·131 Posts
Default

Quote:
Originally Posted by dannyridel View Post
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.
rogue is offline   Reply With Quote
Old 2022-06-03, 16:02   #647
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3×17×131 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2022-06-03, 16:37   #648
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3×17×131 Posts
Default

Quote:
Originally Posted by rogue View Post
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
rogue is offline   Reply With Quote
Old 2022-06-06, 15:09   #649
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

11001110012 Posts
Default

Quote:
Originally Posted by rogue View 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.
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.
Happy5214 is offline   Reply With Quote
Reply

Thread Tools


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔