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

2021-08-13, 17:24   #551
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2·3·5·7·23 Posts

Quote:
 Originally Posted by Plutie Similar? issue to what I reported on page 46 - latest svn Code: /Math/mtsieve$./srsieve2cl -n 100000 -N 500000 -o out.txt -s "(88*10^n-7)/9" srsieve2cl v1.5.3, a program to find factors of k*b^n+c numbers for fixed b and variable k and n Sieving with generic logic for p >= 3 Creating CPU worker to use until p >= 1000000 GPU primes per worker is 25600 Sieve started: 3 < p < 2^62 with 400001 terms (100000 < n < 500000, k*10^n+c) Fatal Error: Invalid factor: (88*10^100000-7)/9 mod 3 = 18446744073709551610 Latest SVN source code is 2.2.2 (July 2nd 2021, r138) The Windows EXE 7z file is 2.2.1 The last commit is r139 Last fiddled with by ET_ on 2021-08-13 at 17:26 2021-08-13, 17:30 #552 Plutie "Evan" Dec 2020 Montreal 71 Posts Quote:  Originally Posted by ET_ Latest SVN source code is 2.2.2 (July 2nd 2021, r138) The Windows EXE 7z file is 2.2.1 The last commit is r139 Just redownloaded r139, same error is occurring. 2021-08-13, 18:27 #553 rogue "Mark" Apr 2003 Between here and the 7·919 Posts Quote:  Originally Posted by Plutie Similar? issue to what I reported on page 46 - latest svn Code: /Math/mtsieve$ ./srsieve2cl -n 100000 -N 500000 -o out.txt -s "(88*10^n-7)/9" srsieve2cl v1.5.3, a program to find factors of k*b^n+c numbers for fixed b and variable k and n Sieving with generic logic for p >= 3 Creating CPU worker to use until p >= 1000000 GPU primes per worker is 25600 Sieve started: 3 < p < 2^62 with 400001 terms (100000 < n < 500000, k*10^n+c) Fatal Error: Invalid factor: (88*10^100000-7)/9 mod 3 = 18446744073709551610
srsieve2 does not work correctly when d > 1. I don't know how easy that will be to fix. I thought it was correct and working but is clearly not.

I do see a separate issue in factor validation when abs(c) > 1, so I will fix that.

Last fiddled with by rogue on 2021-08-13 at 18:49

2021-08-13, 18:30   #554
mathwiz

Mar 2019

3108 Posts

Quote:
 Originally Posted by rogue This is a different issue. I have time to look into it today.
The latest build in SVN seems to be working for me.

However, does gfndsieve respect the -W flag? With -W 36 I still only see a single CPU utilized in "top".

2021-08-13, 19:22   #555
rogue

"Mark"
Apr 2003
Between here and the

7×919 Posts

Quote:
 Originally Posted by mathwiz The latest build in SVN seems to be working for me. However, does gfndsieve respect the -W flag? With -W 36 I still only see a single CPU utilized in "top".
For primes < 1e4 only a single thread is used to reduce contention when removing terms from the vector of remaining terms. But if the first chunk of work ends after 1e4 it will wait until that chunk of work is done. I could modify the code to "rebuild the workers" once it reaches 1e4 so that more threads can do the work.

I would not be surprised if you end up starving workers with -W36 because the main thread that doles out chunks of work will become a bottleneck. One way to offset this is to increase -w to give each worker more to work on.

To eliminate the bottleneck with the main worker would require a number changes to the framework. I haven't thought about it a lot so I don't know how easy or difficult that would be or how much it would impact overall performance.

 2021-08-16, 14:43 #556 mathwiz   Mar 2019 110010002 Posts Unless I'm mistaken about how the ABCD format, gfndsieve seems to be leaving a lot of terms with very small factors. For example, this is a snippet from gfndsieve output: Code: ABCD $a*2^60000+1 [700001] // Sieved to 10000000000051 4 2 2 4 2 2 2 4 2 2 2 2 2 2 4 2 2 2 2 2 2 2 2 4 2 2 4 2 6 Feeding this to LLR gives: Code: 700001*2^60000+1 has a small factor : 3 !! Starting Proth prime test of 700005*2^60000+1 Using all-complex AVX-512 FFT length 6K, a = 7 700005*2^60000+1 is not prime. Base-7 Proth RES64: A386651F7F998E5F. Time : 802.675 ms. 700007*2^60000+1 has a small factor : 3 !! Starting Proth prime test of 700009*2^60000+1 Using all-complex AVX-512 FFT length 6K, a = 3 700009*2^60000+1 is not prime. Proth RES64: B72DF3B16C12AD73. Time : 744.449 ms. 700013*2^60000+1 has a small factor : 3 !! Starting Proth prime test of 700015*2^60000+1 Using all-complex AVX-512 FFT length 6K, a = 3 700015*2^60000+1 is not prime. Proth RES64: E1F28AC9BAA1BB8B. Time : 739.817 ms. Starting Proth prime test of 700017*2^60000+1 Using all-complex AVX-512 FFT length 6K, a = 5 700017*2^60000+1 is not prime. Base-5 Proth RES64: 43CEAF84FFC1C844. Time : 745.082 ms. 700019*2^60000+1 has a small factor : 3 !! Starting Proth prime test of 700023*2^60000+1 Using all-complex AVX-512 FFT length 6K, a = 7 700023*2^60000+1 is not prime. Base-7 Proth RES64: 4B0BB226CE058F90. Time : 755.652 ms. 700025*2^60000+1 has a small factor : 3 !! Starting Proth prime test of 700027*2^60000+1 Using all-complex AVX-512 FFT length 6K, a = 3 700027*2^60000+1 is not prime. Proth RES64: 10DA62863970FCB8. Time : 803.375 ms. 700029*2^60000+1 has a small factor : 5 !! 700031*2^60000+1 has a small factor : 3 !! Note all the "has a small factor : 3 !!" lines.  2021-08-16, 16:23 #557 rogue "Mark" Apr 2003 Between here and the 192116 Posts Is this the latest code in source forge? I'm guessing it is. I'll have to take a look at it. 2021-08-16, 16:26 #558 mathwiz Mar 2019 23·52 Posts Quote:  Originally Posted by rogue Is this the latest code in source forge? I'm guessing it is. I'll have to take a look at it. Yep, latest from SVN. Sample command after building: Code:  ./gfndsieve -P 1e13 -W 36 -n 60000 -N 61000 -k 700e3 -K 800e3 -o gfnsmall.txt Produces: Code: ABCD$a*2^60000+1 [700001] // Sieved to 10000000000051
4
2
2
4
2
2
2
4
2
2
2
2
2
2
...

 2021-08-16, 19:03 #559 rogue     "Mark" Apr 2003 Between here and the 643310 Posts I think I know which code change introduced this, so it shouldn't be too hard to fix. If you need working code, use revision 122.
2021-08-16, 19:10   #560
mathwiz

Mar 2019

C816 Posts

Quote:
 Originally Posted by rogue I think I know which code change introduced this, so it shouldn't be too hard to fix. If you need working code, use revision 122.
Thanks -- but that revision seems to have (build) issues of its own.

Code:
g++ -Isieve -m64 -Wall -O3 -std=c++11 -lstdc++ -o gfndsieve core/App_cpu.o core/FactorApp_cpu.o core/AlgebraicFactorApp_cpu.o core/Clock_cpu.o core/Parser_cpu.o core/Worker_cpu.o core/HashTable_cpu.o core/main_cpu.o core/SharedMemoryItem_cpu.o sieve/Erat.o sieve/EratBig.o sieve/EratMedium.o sieve/EratSmall.o sieve/PreSieve.o sieve/CpuInfo.o sieve/MemoryPool.o sieve/PrimeGenerator.o sieve/PrimeSieve.o sieve/IteratorHelper.o sieve/LookupTables.o sieve/popcount.o sieve/nthPrime.o sieve/PrintPrimes.o sieve/ParallelSieve.o sieve/iterator.o sieve/api.o sieve/SievingPrimes.o x86_asm/fpu_mod_init_fini.o x86_asm/fpu_push_pop.o x86_asm/sse_mulmod.o x86_asm/fpu_mulmod.o x86_asm/fpu_powmod.o x86_asm/fpu_powmod_4b_1n_4p.o x86_asm/fpu_mulmod_iter.o x86_asm/fpu_mulmod_iter_4a.o x86_asm/fpu_mulmod_4a_4b_4p.o x86_asm/sse_mod_init_fini.o x86_asm/sse_powmod_4b_1n_4p.o x86_asm/sse_mulmod_4a_4b_4p.o x86_asm/avx_set_a.o x86_asm/avx_set_b.o x86_asm/avx_get.o x86_asm/avx_compute_reciprocal.o x86_asm/avx_compare.o x86_asm/avx_mulmod.o x86_asm/avx_powmod.o x86_asm/sse_powmod_4b_1n_4p_mulmod_1k.o x86_asm_ext/m320.o x86_asm_ext/m384.o x86_asm_ext/m448.o x86_asm_ext/m512.o x86_asm_ext/m576.o x86_asm_ext/m640.o x86_asm_ext/m704.o x86_asm_ext/m768.o x86_asm_ext/mulmod128.o x86_asm_ext/mulmod192.o x86_asm_ext/mulmod256.o x86_asm_ext/sqrmod128.o x86_asm_ext/sqrmod192.o x86_asm_ext/sqrmod256.o x86_asm_ext/redc.o gfn_divisor/GFNDivisorApp_cpu.o gfn_divisor/GFNDivisorWorker_cpu.o  -lgmp -lpthread
/usr/bin/ld: gfn_divisor/GFNDivisorApp_cpu.o: in function GFNDivisorApp::PostSieveHook()':
GFNDivisorApp.cpp:(.text+0x3b1): undefined reference to GFNDivisorTester::TestRemainingTerms(unsigned long, unsigned long, unsigned long)'
/usr/bin/ld: gfn_divisor/GFNDivisorApp_cpu.o: in function GFNDivisorApp::ValidateOptions()':
GFNDivisorApp.cpp:(.text+0x292c): undefined reference to GFNDivisorTester::GFNDivisorTester(App*)'
/usr/bin/ld: gfn_divisor/GFNDivisorApp_cpu.o: in function GFNDivisorApp::PreSieveHook()':
GFNDivisorApp.cpp:(.text+0x20d8): undefined reference to GFNDivisorTester::StartedSieving()'
collect2: error: ld returned 1 exit status
I'm in no rush, so happy to wait for a fix at head.

 2021-08-16, 22:34 #561 rogue     "Mark" Apr 2003 Between here and the 7·919 Posts You would need all of the sources from that revision to build it. On the positive side this issue is now fixed. I was over-thinking a speed up in the previous revision for small primes and it was just plain stupid. It was never going to work. It works now based upon the testing I have done.

All times are UTC. The time now is 16:04.

Sun Oct 24 16:04:05 UTC 2021 up 93 days, 10:33, 0 users, load averages: 1.05, 1.50, 1.62