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

150268 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

2×32×7×53 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

150268 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

2×32×7×53 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:	36
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

11010000101102 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
Old 2022-07-17, 19:44   #656
japelprime
 
japelprime's Avatar
 
"Erling B."
Dec 2005

25×3 Posts
Default fbncsieve

I was looking at fkbncsieve. In the html multi- threaded sieve framework link it says this program is for both k*b^n+1 and k*b^n-1 form. Using Command prompt and fbncsieve -h it says k*b^n+c form. Is there any -1 or +1 switch for fbncsieve win batch file for some of the mtsieve programs. I was just thinking of start sieving k*b^n-1 from scratch without any "-i" input file and also later with input file.

C:\EB\Prime\mtsieve\mtsieve_2.3.2 - profa>fkbnsieve -h
fkbnsieve v1.4, a program to find factors of k*b^n+c numbers for fixed k, b, and n and variable c
-h --help prints this help
-p --pmin=P0 sieve start: P0 < p (default 1)
-P --pmax=P1 sieve end: p < P1 (default 2^62)
-w --worksize=w primes per chunk of work (default 1000000)
-W --workers=W start W workers (default 0)
-A --applyandexit apply factors and exit (used with -I)
-i --inputterms=i input file of remaining candidates
-I --inputfactors=I input file with factors (used with -A)
-o --outputterms=o output file of remaining candidates
-O --outputfactors=O output file with new factors
-c --cmin=c Minimum c to search
-C --cmax=C Maximum c to search
-s --sequence=s Sequence to find factors of in form k*b^n+c where k, b, and n are integer values

Last fiddled with by japelprime on 2022-07-17 at 19:47
japelprime is offline   Reply With Quote
Old 2022-07-17, 22:48   #657
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·32·7·53 Posts
Default

Quote:
Originally Posted by japelprime View Post
I was looking at fkbncsieve. In the html multi- threaded sieve framework link it says this program is for both k*b^n+1 and k*b^n-1 form. Using Command prompt and fbncsieve -h it says k*b^n+c form. Is there any -1 or +1 switch for fbncsieve win batch file for some of the mtsieve programs. I was just thinking of start sieving k*b^n-1 from scratch without any "-i" input file and also later with input file.

C:\EB\Prime\mtsieve\mtsieve_2.3.2 - profa>fkbnsieve -h
fkbnsieve v1.4, a program to find factors of k*b^n+c numbers for fixed k, b, and n and variable c
-h --help prints this help
-p --pmin=P0 sieve start: P0 < p (default 1)
-P --pmax=P1 sieve end: p < P1 (default 2^62)
-w --worksize=w primes per chunk of work (default 1000000)
-W --workers=W start W workers (default 0)
-A --applyandexit apply factors and exit (used with -I)
-i --inputterms=i input file of remaining candidates
-I --inputfactors=I input file with factors (used with -A)
-o --outputterms=o output file of remaining candidates
-O --outputfactors=O output file with new factors
-c --cmin=c Minimum c to search
-C --cmax=C Maximum c to search
-s --sequence=s Sequence to find factors of in form k*b^n+c where k, b, and n are integer values
Not certain that I understand your question. You can use -1 or +1 for "+c".
rogue is offline   Reply With Quote
Old 2022-07-18, 01:03   #658
japelprime
 
japelprime's Avatar
 
"Erling B."
Dec 2005

25·3 Posts
Default

Quote:
Originally Posted by rogue View Post
Not certain that I understand your question. You can use -1 or +1 for "+c".
Of course. Silly me.
Thanks.
japelprime is offline   Reply With Quote
Old 2022-07-18, 14:26   #659
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

11010000101102 Posts
Default

I have finally released mtsieve 2.3.3. Changes include:

Code:
   framework:
      Updated primesieve to 7.9.  This addresses an issue in primesieve that can crash
      the mtsieve applications.
      
      Changed usage of primesieve (thanks to hints from Kim Wallisch, its creator) to
      improve sieving peformance.  As a result the worker threads now use an array instead
      of a vector.
      
      Broke the main sieving loop into two loops, one for when limited to a single thread
      or for sieving prior to switching to the GPU.  The second loop handles multiple worker
      threads much better.
      
      Reduced the initial CPU worksize from 1e6 to 96e3.  When the largest prime tested
      reaches 1e6, the worker thread can automatically adjust the worksize in an effort
      to have each chunk take between 1 and 5 seconds to process.  This has two affects.
      First, it will allow the CPU workers to stop more quickly when the user hits ^C.
      Second, it will do a better job at keeping CPU workers busy when using mulitple workers.
 
   fkbnsieve: version 1.5
      Only verify the first few factors found for each prime to speed up initial sieve.

   sgsieve: version 1.3
      Changed to support p/2p+1 where p is of the form k*b^n-1.  This makes it compatible
      with newpgen.  As of 1.2 p was of the form k*b^n+1.

   srsieve2: vesion 1.6.3
      Default to not use Legendre tables for multiple sequences unless -l is used.
I have still not completed the Metal changes with testing. It has been a busy summer so I can't get that to the finish line. I think it is close.
I just need to have the time and motivation to finish. The sieves with no x86 ASM will compile on ARM and thus on Apple's M1/M2 CPUs.
rogue is offline   Reply With Quote
Old 2022-07-18, 23:34   #660
japelprime
 
japelprime's Avatar
 
"Erling B."
Dec 2005

1408 Posts
Default

I notice trouble with the ^ sign for me in batch file. Maybe this error outcome is regarding my wrong format for k*b^n+c but I am not sure what is wrong when the output file is not the same as input.
command promt shows -s k*21964-1 (without powerfaktor ^) but my batch file is written with k*2^1964-1

Command prompt:
C:\EB\Prime\mtsieve\fbncsieve_minus_1964>fbncsieve.exe -s k*21964-1 -k 1 -K 4000000 -P 10e14 -o remaining_faktors_prufa.txt
fbncsieve v1.4, a program to find factors of k*b^n+c numbers for fixed b, n, and c and variable k
Fatal Error: sequence must be in form k*b^n+c where you specify values for b, n and c

Last fiddled with by japelprime on 2022-07-18 at 23:39
japelprime is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 02:06.


Mon Aug 8 02:06:19 UTC 2022 up 31 days, 20:53, 1 user, load averages: 1.47, 1.44, 1.21

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.

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