mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Software (https://www.mersenneforum.org/forumdisplay.php?f=10)
-   -   mtsieve (https://www.mersenneforum.org/showthread.php?t=23042)

axn 2022-05-27 05:03

[QUOTE=dannyridel;606614]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)?[/QUOTE]

No. Only (p, 2p+1) is SG

[QUOTE=rogue;606553]Sophie Germain: A prime p is said to be a Sophie Germain prime if both p and 2p+1 are prime.[/QUOTE]

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

rogue 2022-05-27 13:15

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
[/code]

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 [URL="https://mathworld.wolfram.com/CunninghamChain.html"]MathWorld[/URL]), 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.

Happy5214 2022-05-29 15:25

Regarding the ARM version, what ever happened to the ARM ASM routines I sent you? Those were supposed to be translations of the [c]fpu_*.S[/c] files for x86. Did those not work?

Edit: They were attached to [url=https://www.mersenneforum.org/showpost.php?p=567515&postcount=71]this post[/url].

rogue 2022-05-30 00:11

[QUOTE=Happy5214;606780]Regarding the ARM version, what ever happened to the ARM ASM routines I sent you? Those were supposed to be translations of the [c]fpu_*.S[/c] files for x86. Did those not work?

Edit: They were attached to [url=https://www.mersenneforum.org/showpost.php?p=567515&postcount=71]this post[/url].[/QUOTE]

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.

dannyridel 2022-06-02 16:01

[QUOTE=rogue;606636]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
[/code]

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.[/QUOTE]

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

rogue 2022-06-02 16:35

[QUOTE=dannyridel;607014]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...[/QUOTE]

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.

dannyridel 2022-06-03 01:38

[QUOTE=rogue;607015]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.[/QUOTE]


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?

rogue 2022-06-03 12:28

[QUOTE=dannyridel;607048]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?[/QUOTE]

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 2022-06-03 16:02

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.
[/code]

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 2022-06-03 16:37

[QUOTE=rogue;607083]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.[/QUOTE]

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.

Happy5214 2022-06-06 15:09

[QUOTE=rogue;606800]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.[/QUOTE]

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 [C]-O2[/C], and at least on [C]REDC[/C] and [C]mul[/C] 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 22:17.

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