mersenneforum.org  

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

Reply
 
Thread Tools
Old 2022-06-06, 15:39   #650
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·5·443 Posts
Default

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

3×5×443 Posts
Default

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 is offline   Reply With Quote
Old 2022-06-07, 14:55   #652
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·5·443 Posts
Default

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 is offline   Reply With Quote
Old 2022-06-07, 18:38   #653
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

664510 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2022-06-08, 18:59   #654
twobombs
 
Jun 2022

2 Posts
Default

Quote:
Originally Posted by rogue View Post
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
Click image for larger version

Name:	Screenshot from 2022-06-08 20-53-10.png
Views:	28
Size:	48.1 KB
ID:	26988  
twobombs is offline   Reply With Quote
Old 2022-06-08, 19:36   #655
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3×5×443 Posts
Default

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

Thread Tools


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

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.

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