A possible bug in LLR/PFGW while using GWNUM (no bug in P95) - Page 2

Batalov · 2014-12-15, 22:15

gp> (log(1024)+ log(3)*1877301 )/log(10)
895703.21890643365300834531519767847000

895704 is correct.

After some discussions with Prof.Caldwell, he indeed revived the number.

I put the comment there that summarizes the evidence gathered so far. It seems something is going on with AVX portion of GWNUM lib, but the PRP test implementation in the latest P95 is not affected! maybe LLR and PFGW are not initializing something correctly up to the latest API? (like setting max mulitplier or something comes to mind)

Just a note added in proof: all tests were done on ECC-endowed computers, so we can rule out bad memory or memory communications.

Batalov · 2014-12-15, 22:18

Quote:

Originally Posted by Prime95

I ran this using prime95 version 28.5 with AVX but not FMA FFTs. Prime95 chose a 240K FFT size. Round off error was only 0.02. It worked.

My conclusion is the problem is not in choosing an FFT size that is too small. Either a GWNUM bug was fixed between 27.9 and 28.5 or PFGW's PRP code is doing something subtly different than prime95's and either has a bug or reveals a bug in GWNUM.

I'm a little confused about what is failing in PFGW. Does PFGW report it as a PRP or is the problem only in the N-1 proving code?

No, for a while (before it was removed) there was a full output from C.C.'s Xeon-based PFGW.
He used 3.7.7 with 27.9 gwnum, iirc, but I didn't save a screenshot. PFGW was called with -t (so it is B-L-S N-1 without preliminary PRP test) and without -a1 or -a2, but a bit later C.C. reported that those runs returned 'composite' too.

paulunderwood · 2014-12-15, 22:23

Quote:

Originally Posted by paulunderwood

Code:

 wc Serge
     1      1 895705 Serge

Doh. There seems to be a newline in my file!

rogue · 2014-12-15, 22:57

Which version of pfgw is showing this as composite? Do you know which FFT size it selected?

Batalov · 2014-12-15, 23:50

It is hard to say the FFT size (the -v option doesn't increase verboseness, it is for other use).

But here's my most recent run with the freshly minted PFGW (and -a1):

Code:

PFGW Version 3.7.8.64BIT.20141125.x86_Dev [GWNUM 28.5]

Output logging to file pfgw.out

Primality testing 1024*3^1877301+1 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 5
1024*3^1877301+1 is prime! (12669.4555s+0.0219s)

I haven't saved the PFGW output from UTM, and now it is removed.
Here's something we can use: my kernel data is:
Linux ws2 2.6.32.12-0.7-default #1 SMP 2010-05-20 11:14:20 +0200 x86_64 x86_64 x86_64 GNU/Linux
model name : Intel(R) Xeon(R) CPU X5660 @ 2.80GHz
stepping : 2
cpu MHz : 2792.602
cache size : 12288 KB
(Note: 2.6.32 means that AVX is enabled; need >= 2.6.18)
EDIT: never mind that it may be enabled -- this CPU is from 2010; it doesn't have AVX.

Let's see what UTM Xeon server has... (e.g. using very recent data here)
Using: Xeon 4c+4c 3.5GHz <-- Hmmm, local lingo
Command: /home/caldwell/client/pfgw/pfgw64 -t -q"2378*3^960224+1" 2>&1
PFGW Version 3.7.7.64BIT.20130722.x86_Dev [GWNUM 27.11]
Primality testing 2378*3^960224+1 [N-1, Brillhart-Lehmer-Selfridge]
...
The same version was used on the last number.

rogue · 2014-12-16, 02:50

Try -V instead of -v.

Batalov · 2014-12-16, 03:22

On my comp, the non-AVX 256K size is used:

Code:

Primality testing 1024*3^1877301+1 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 5
Special modular reduction using all-complex Pentium4 FFT length 256K, Pass1=256, Pass2=1K on 1024*3^1877301+1

I'll ask C.C.

I am almost done with non-AVX LLR runs in four bases and with FFT two sizes (256K and 288K). Will update here, in an hour:

Code:

1024*3^1877301+1 may be prime, but N divides 3^((N-1)/3))-1, restarting with a=5  Time : 9560.093 sec.

Base prime factor(s) taken : 3
Starting N-1 prime test of 1024*3^1877301+1
1024*3^1877301+1 may be prime, trying to compute gcd's
5^((N-1)/3)-1 is coprime to N!
1024*3^1877301+1 is prime! (895704 decimal digits)  Time : 9524.973 sec.

Base prime factor(s) taken : 3
Starting N-1 prime test of 1024*3^1877301+1
1024*3^1877301+1 may be prime, trying to compute gcd's
7^((N-1)/3)-1 is coprime to N!
1024*3^1877301+1 is prime! (895704 decimal digits)  Time : 9521.660 sec.

Base prime factor(s) taken : 3
Starting N-1 prime test of 1024*3^1877301+1
1024*3^1877301+1 may be prime, trying to compute gcd's
11^((N-1)/3)-1 is coprime to N!
1024*3^1877301+1 is prime! (895704 decimal digits)  Time : 9519.687 sec.

Base prime factor(s) taken : 3
Starting N-1 prime test of 1024*3^1877301+1
1024*3^1877301+1 may be prime, trying to compute gcd's
1024*3^1877301+1 may be prime, but N divides 17^((N-1)/3))-1, restarting with a=19  Time : 9514.177 sec.
Restarting N-1 prime test of 1024*3^1877301+1
...

and the same results with FFT_Increment=1 (i.e. 288K FFT), only longer times, obviously

paulunderwood · 2014-12-17, 20:29

I get a mismatch of RES64's:

Code:

./pfgw_ver_12_linux -q"2*3^90420+1"
PFGW Version 1.2.0 for Pentium and compatibles [FFT v23.8]

2*3^90420+1 is composite: [3756EDC5668626CF] (47.7282s+0.0011s)

Code:

 ./pfgw64 -q"2*3^90420+1"
PFGW Version 3.7.7.64BIT.20130722.x86_Dev [GWNUM 27.11]

2*3^90420+1 is composite: RES64: [7756EDC5668626CF] (8.2449s+0.0047s)

And silence if I run:

Code:

./pfgw_ver_12_linux -q"2*3^90421+1"
PFGW Version 1.2.0 for Pentium and compatibles [FFT v23.8]

^C

I get these mismatches too:

Code:

./pfgw64 -q"2*3^90419+1"
PFGW Version 3.7.8.64BIT.20141125.x86_Dev [GWNUM 28.5]

2*3^90419+1 is composite: RES64: [17F958B71309C04A] (10.0592s+0.0003s)

Code:

./pfgw64 -q"2*3^90419+1"
PFGW Version 3.7.7.64BIT.20130722.x86_Dev [GWNUM 27.11]

2*3^90419+1 is composite: RES64: [03FBCEF4D1C55728] (10.5805s+0.0003s)

I also ran a "-t" test with 3.7.7.64BIT.20130722.x86_Dev on Serge's problem number and noticed it took a long time to compute "F", which is silly!

Batalov · 2014-12-17, 21:46

1. Mark would appreciate if you add -V to the command lines.
(Then the FFT size and AVX / non-AVX would be easily seen.)

2. By adding InterimResidues=N to llr.ini, I've found that interim residues are simply incompatible! Incompatible between different FFT sizes, and incompatible between AVX / non-AVX runs.* That is: even if the result is correct and a test is run to the end and returns "P" for e.g. 4096*3^208687+1, the interim residues are all different. The last matching row is "bit 28" (in these tests, not iterations, but bits of the exponents are being numbered). Before bit 28, the small interim residues are trivially correct, e.g. if FermatBase=5, they start with 25, 625, 390625, etc in hex. For 3, the familiar values of 9, 81, etc (or depending on the input number, one can see small odd powers of the FermatBase)... but after bit 28, all becomes incompatible (yet, of course, reproducible, -- if you run the same, twice).

I had not enough time last night to understand why interim residues don't match.

3. Parallel line of investigation: does Prime95-based PRP work on AVX CPUs for this particular debug case (1024*3^1877301+1 **)?
(In other words, is the bug simply in GWNUM, or is it in how GWNUM is used.)
The answer is: yes! Prime95-based PRP works fine in bases 3,5,7,11 both AVX / non-AVX.
In other words, the library FFT for 224K, 256K, 288K sizes is not trivially (say a typo) broken.

This is what I know so far.
______________
*Footnote: in the region of interest, that is at least above 90,000 digits input sizes.
For small inputs, miraculously, interim residues are exactly identical (for numbers in the FFT ranges 3K, 4K, 5K).

**I searched for a smaller example of numbers of form 2^m*3^n+1 (m<=16, n large) that would fail LLR test and didn't find. I had found these to test:
16384*3^24093+1
65536*3^200115+1
4096*3^208687+1
2048*3^229654+1
65536*3^232379+1 -- they all pass LLR, PFGW, Prime95 just fine; AVX or non-AVX

Batalov · 2014-12-18, 01:35

An additional test of George's idea is in progress.

Quote:

Originally Posted by Prime95

My guess at this point is this is one of those numbers with a "problematic" bit pattern and both pfgw and llr during their first few iterations of the N-1 test are not using square_carefully and mul_carefully. Prime95 avoids the issue by using square_carefully and mul_carefully for the first 50 and last 50 iterations of the PRP test.

George's code in Prime95 passes the bug report number for the PRP test (which is essentially no different from N-1): both on AVX and non-AVX CPUs.

Indeed, LLR runs 30 rounds of guarded/careful squares in the Proth test (see line 10669 in Llr.c); I upped this number to 60 and I am rerunning. 30 and Nlen-30 (and variations, e.g. 31) are used in other tests as well; all of them may need to be increased as the average sizes of prime candidates increased over last years.

EDIT: this idea was a dead end; the result is the same (30 or 60 guarded iterations). What is more depressing the final "RES64" is different for different FFT sizes. Maybe I'll try to go -a3, -a4, -a5 and so on. (in llr.ini, FFT_Increment=3,4,5...)

paulunderwood · 2014-12-18, 04:02

Some good news:

Code:

 ./pfgw64 -tp -i -V -q"1024*3^1877301+1"
PFGW Version 3.7.7.64BIT.20130722.x86_Dev [GWNUM 27.11]


CPU Information (From Woltman v26 library code)
Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz
CPU speed: 3721.69 MHz, 4 cores
CPU features: RDTSC, CMOV, Prefetch, MMX, SSE, SSE2, SSE4.1, SSE4.2
L1 cache size: 32 KB
L2 cache size: 256 KB, L3 cache size: 8 MB
L1 cache line size: 64 bytes
L2 cache line size: 64 bytes
TLBS: 64
                                    
Primality testing 1024*3^1877301+1 [N+1, Brillhart-Lehmer-Selfridge]                                    
Running N+1 test using discriminant 5, base 5+sqrt(5)                                    
Special modular reduction using all-complex AVX FFT length 240K, Pass1=1280, Pass2=192 on 1024*3^1877301+1                                    
1024*3^1877301+1 is Lucas PRP! (24654.3415s+0.0223s)

2014-12-15, 22:15	#12
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 19·23² Posts	gp> (log(1024)+ log(3)1877301 )/log(10) 895703.21890643365300834531519767847000 895704 is correct. After some discussions with Prof.Caldwell, he indeed revived the number. I put the comment there that summarizes the evidence gathered so far. It seems something is going on with AVX portion of GWNUM lib, but the PRP test implementation in the latest P95 is not affected! maybe LLR and PFGW are not initializing something correctly up to the latest API? (like setting max mulitplier or something comes to mind) Just a note added in proof: all tests were done on ECC-endowed computers, so we can rule out bad memory or memory communications. Last fiddled with by Batalov on 2014-12-15 at 22:24*

2014-12-15, 23:50	#16
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10011101000011₂ Posts	It is hard to say the FFT size (the -v option doesn't increase verboseness, it is for other use). But here's my most recent run with the freshly minted PFGW (and -a1): Code: PFGW Version 3.7.8.64BIT.20141125.x86_Dev [GWNUM 28.5] Output logging to file pfgw.out Primality testing 10243^1877301+1 [N-1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 5 10243^1877301+1 is prime! (12669.4555s+0.0219s) I haven't saved the PFGW output from UTM, and now it is removed. Here's something we can use: my kernel data is: Linux ws2 2.6.32.12-0.7-default #1 SMP 2010-05-20 11:14:20 +0200 x86_64 x86_64 x86_64 GNU/Linux model name : Intel(R) Xeon(R) CPU X5660 @ 2.80GHz stepping : 2 cpu MHz : 2792.602 cache size : 12288 KB (Note: 2.6.32 means that AVX is enabled; need >= 2.6.18) EDIT: never mind that it may be enabled -- this CPU is from 2010; it doesn't have AVX. Let's see what UTM Xeon server has... (e.g. using very recent data here) Using: Xeon 4c+4c 3.5GHz <-- Hmmm, local lingo Command: /home/caldwell/client/pfgw/pfgw64 -t -q"23783^960224+1" 2>&1 PFGW Version 3.7.7.64BIT.20130722.x86_Dev [GWNUM 27.11] Primality testing 23783^960224+1 [N-1, Brillhart-Lehmer-Selfridge] ... The same version was used on the last number. Last fiddled with by Batalov on 2014-12-16 at 03:46

2014-12-17, 21:46	#20
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10051₁₀ Posts	1. Mark would appreciate if you add -V to the command lines. (Then the FFT size and AVX / non-AVX would be easily seen.) 2. By adding InterimResidues=N to llr.ini, I've found that interim residues are simply incompatible! Incompatible between different FFT sizes, and incompatible between AVX / non-AVX runs.* That is: even if the result is correct and a test is run to the end and returns "P" for e.g. 40963^208687+1, the interim residues are all different. The last matching row is "bit 28" (in these tests, not iterations, but bits of the exponents are being numbered). Before bit 28, the small interim residues are trivially correct, e.g. if FermatBase=5, they start with 25, 625, 390625, etc in hex. For 3, the familiar values of 9, 81, etc (or depending on the input number, one can see small odd powers of the FermatBase)... but after bit 28, all becomes incompatible (yet, of course, reproducible, -- if you run the same, twice). I had not enough time last night to understand why interim residues don't match. 3. Parallel line of investigation: does Prime95-based PRP work on AVX CPUs for this particular debug case (10243^1877301+1 *)? (In other words, is the bug simply in GWNUM, or is it in how* GWNUM is used.) The answer is: yes! Prime95-based PRP works fine in bases 3,5,7,11 both AVX / non-AVX. In other words, the library FFT for 224K, 256K, 288K sizes is not trivially (say a typo) broken. This is what I know so far. ______________ Footnote: in the region of interest, that is at least above 90,000 digits input sizes. For small inputs, miraculously, interim residues are exactly identical (for numbers in the FFT ranges 3K, 4K, 5K). I searched for a smaller example of numbers of form 2^m3^n+1 (m<=16, n large) that would fail LLR test and didn't find. I had found these to test: 163843^24093+1 655363^200115+1 40963^208687+1 20483^229654+1 655363^232379+1 -- they all pass LLR, PFGW, Prime95 just fine; AVX or non-AVX Last fiddled with by Batalov on 2014-12-17 at 22:00 Reason: closed paren, added more details to item 2*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
PFGW 4.0.4 (with gwnum v30.10) Released	rogue	Software	545	2023-01-20 14:12
LLR V3.8.2 using gwnum 26.2 is available!	Jean Penné	Software	25	2010-11-01 15:18
PFGW 3.3.6 or PFGW 3.4.2 Please update now!	Joe O	Sierpinski/Riesel Base 5	5	2010-09-30 14:07
GWNUM?	Unregistered	Information & Answers	3	2010-09-12 19:52
GWNUM as DLL?	Cyclamen Persicum	Software	1	2007-01-02 20:53

2014-12-15, 22:57	#15
rogue "Mark" Apr 2003 Between here and the 1B30₁₆ Posts	Which version of pfgw is showing this as composite? Do you know which FFT size it selected?

2014-12-16, 02:50	#17
rogue "Mark" Apr 2003 Between here and the 1101100110000₂ Posts	Try -V instead of -v.