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

2022-06-06, 15:39   #650
rogue

"Mark"
Apr 2003
Between here and the

3·2,273 Posts

Quote:
 Originally Posted by Happy5214 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.

 2022-06-06, 16:10 #651 rogue     "Mark" Apr 2003 Between here and the 3×2,273 Posts 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.
 2022-06-07, 14:55 #652 rogue     "Mark" Apr 2003 Between here and the 3·2,273 Posts 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.
 2022-06-07, 18:38 #653 rogue     "Mark" Apr 2003 Between here and the 681910 Posts 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.
2022-06-08, 18:59   #654
twobombs

Jun 2022

2 Posts

Quote:
 Originally Posted by rogue 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

2022-06-08, 19:36   #655
rogue

"Mark"
Apr 2003
Between here and the

1AA316 Posts

Quote:
 Originally Posted by twobombs 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.

 2022-07-17, 19:44 #656 japelprime     "Erling B." Dec 2005 103 Posts 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
2022-07-17, 22:48   #657
rogue

"Mark"
Apr 2003
Between here and the

3·2,273 Posts

Quote:
 Originally Posted by japelprime 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".

2022-07-18, 01:03   #658
japelprime

"Erling B."
Dec 2005

11001112 Posts

Quote:
 Originally Posted by rogue Not certain that I understand your question. You can use -1 or +1 for "+c".
Of course. Silly me.
Thanks.

 2022-07-18, 14:26 #659 rogue     "Mark" Apr 2003 Between here and the 3×2,273 Posts 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.
 2022-07-18, 23:34 #660 japelprime     "Erling B." Dec 2005 103 Posts 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

All times are UTC. The time now is 17:19.

Thu Dec 1 17:19:02 UTC 2022 up 105 days, 14:47, 1 user, load averages: 0.96, 1.16, 1.21

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.

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