mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-08-13, 17:24   #551
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2·3·5·7·23 Posts
Default

Quote:
Originally Posted by Plutie View Post
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
ET_ is offline   Reply With Quote
Old 2021-08-13, 17:30   #552
Plutie
 
"Evan"
Dec 2020
Montreal

71 Posts
Default

Quote:
Originally Posted by ET_ View Post
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.
Plutie is offline   Reply With Quote
Old 2021-08-13, 18:27   #553
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3×19×113 Posts
Default

Quote:
Originally Posted by Plutie View Post
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
rogue is offline   Reply With Quote
Old 2021-08-13, 18:30   #554
mathwiz
 
Mar 2019

3×67 Posts
Default

Quote:
Originally Posted by rogue View Post
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".
mathwiz is offline   Reply With Quote
Old 2021-08-13, 19:22   #555
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·19·113 Posts
Default

Quote:
Originally Posted by mathwiz View Post
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.
rogue is offline   Reply With Quote
Old 2021-08-16, 14:43   #556
mathwiz
 
Mar 2019

3·67 Posts
Default

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.
mathwiz is offline   Reply With Quote
Old 2021-08-16, 16:23   #557
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

144518 Posts
Default

Is this the latest code in source forge? I'm guessing it is. I'll have to take a look at it.
rogue is offline   Reply With Quote
Old 2021-08-16, 16:26   #558
mathwiz
 
Mar 2019

3118 Posts
Default

Quote:
Originally Posted by rogue View Post
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
...
mathwiz is offline   Reply With Quote
Old 2021-08-16, 19:03   #559
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·19·113 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2021-08-16, 19:10   #560
mathwiz
 
Mar 2019

3×67 Posts
Default

Quote:
Originally Posted by rogue View Post
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.
mathwiz is offline   Reply With Quote
Old 2021-08-16, 22:34   #561
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3×19×113 Posts
Default

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.
rogue is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 22:49.


Wed Oct 27 22:49:25 UTC 2021 up 96 days, 17:18, 0 users, load averages: 1.60, 1.21, 1.04

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.