Don't DC/LL them with CudaLucas

LaurV · 2011-12-02, 07:46

This thread is a follow of the discussions started here.

This is the list of exponents that were DC-ed with CudaLucas or other third party software and the residue did not match. They can only be DC-ed further using Prime95 (or its flavors). Do not waste your time DC-ing them with the GPU, this will not clear the exponent, except in the case you get the original residue (and not the one got by former CudaLucas run, which in fact, you will most probably get).

Code:

exponent, date, reported by who:
=========================
25891057  2011-12-02  moebius - cleared
26044199  2012-01-29  LaurV - cleared by GIMPS Visualization 2012-02-10
26087059  2012-01-30  flashjh  - cleared by 1997rj7 2012-02-26
26116807  2012-01-30  flashjh
26123989  2012-01-13  LaurV - cleared by Aaron Haviland 2012-01-26
26124271  2012-01-29  LaurV - cleared by diamonddave 2012-04-14
26126813  2012-01-30  flashjh
26141813  2012-02-01  flashjh - cleared by monst on 2012-02-26
26269081   - LaurV the CL residue should be the right one (see post 33) - please notify me when you complete a P95 test for this expo.
26147579  2012-01-29  LaurV - cleared by monst 2012-02-07 - original residue was OK!
26830123  2011-12-01  LaurV - cleared by Helmut Kirrmaier 2011-12-14

Next is the list of exponents LL-ed (first time LL) with CudaLucas. They can only be Double-Checked using Prime95 (or its flavors). Do not waste your time DC-ing them with the GPU, this will not clear the exponent even if you get the same residue.

Code:

exponent, date, reported by who:
=========================
45061487  2012-01-30  LaurV - cleared by kdgehman on 2012-05-08
45089339  2012-01-30  LaurV
45097049  2012-01-30  LaurV
45179867  2012-01-30  LaurV
46678811  2011-12-02  moebius
46738091  2011-12-02  moebius - cleared
47842481  2011-12-02  moebius
49052579  2011-12-02  moebius
49054861  2011-12-02  moebius
49190957  2011-12-13  moebius
49997309  2011-12-02  moebius
50217353  2011-12-02  moebius
50217379  2011-12-02  moebius
50636153  2011-12-02  moebius
51936263  2011-12-02  moebius
51936497  2011-12-02  moebius
54371311  2012-01-30  LaurV
56173303  2011-12-13  LaurV
56173339  2011-12-02  LaurV

I would take the responsibility to maintain this list if some god here (xyzzy? are you around? :P) gives me the mod rights. This involve in fact editing the first post only, for an unlimited period of time (beside of hunting the forum for the posts including such exponents, when they are not posted in the current thread, sorting them in the list, etc).

moebius · 2011-12-02, 09:27

For
25891057 the residue did match, but what about triple-checks?

ET_ · 2011-12-02, 09:58

I had different behaviors with CUDALucas.

Some tests ended with a correct residue, some didn't.

As it is fairly hard that 2 numbers end up with the same wrong residue, I suppose that CUDALucas is not that bad.

Luigi

Brian-E · 2011-12-02, 11:15

Quote:

Originally Posted by ET_

As it is fairly hard that 2 numbers end up with the same wrong residue, I suppose that CUDALucas is not that bad.

Luigi

The point, if I understand it correctly, is that there is as yet no safeguard in CUDALucas to insure against precisely this happening. If some obscure software bug were to cause an incorrect calculation at some point in the test, a subsequent test by a different user could repeat this incorrect calculation and produce the same wrong result. Prime95/mprime by contrast starts the LL test with a random offset so that this will not happen. (Those more knowledgeable than I am please put me right if I've stated this incorrectly.)

LaurV · 2011-12-02, 16:07

You did not state it incorrectly, you put it very correctly.

Prime95 will choose a random number k between 0 and p-1 and will rotate each residue inside of the p bits you have, with k bits. Then it will square the result. At the end you get the residue rotated with 2k bits. This ensure that the FFT deal with different data each time, so if there is a software bug in it, it would be almost impossible to produce the same result (unique up to a rotation) for the final residue.

You can square a number x and take the result mod M, where M=2^p-1, to get x^2 (mod M). Now, if you square 2^k*x, you get 2^(2*k)*x^2. But the order of 2 in M is p, because 2^p=1 (mod M), so you get in fact 2^(2*k (mod p))*x^2 (mod M), where the (mod p) is at the power, i.e. 2*k is taken (mod p). Now if you note that x=y (mod M) means x=a*M+y, you can write x=a*(M+1)-a+y. Think at that like modulo M+1, which is 2^p, this means you can find y by adding the last p bits of x with the other bits of x. This is in fact a rotation of x^2 with 2k bits.

Example: for p=13, M=8191, the "standard" test gives the series of residues:
4,14,194,4870,3953,5970,1857,36,1294,3470,128,0
If you shift the initial value with 1 bit to the left (k=1) what you get is
8,56,3104,1688,7051,5294,5024,9,7248,4557,16,0
In this case the number is prime, and the residue is always 0.

For p=11, M=2047, the "standard" tests gives
4,14,194,788,701,119,1877,240,282,1736
and the "rotated by k=1" test gives
8,56,1057,1122,1962,1083,981,15,209,566

If you look to the binary representations of the two final residues, they are "the same up to a rotation with 5 positions". Where does 5 come from, you can compute, and indeed, if you rotate the second result 5 positions to the left, you get the first.
1736 = binary 110 1100 1000
0566 = binary 010 0011 0110

So, P95 goes through all this trouble for each term in the LL sequence of residues, to ensure that FFT squaring deals with different data each time when you LL or DC. CudaLucas does not. It always starts with 4, square it, subtract 2, square it, subtract 2, etc. A bug (or overflow, or whatever) in the FFT code will produce always the same error in the "square it" step. Therefore always the same (wrong) residue. Prime95 can produce a number of p different residues (internally), if you run it so many times for the same exponent, because it will pick a (different) random k each time. The residues have to match after P95 rotates them with the right number of bits, and communicate them to you.

bcp19 · 2011-12-02, 16:15

I know I ran a few DC on my GPU prior to GPUto72 and had 1 mismatch, but I had been adjusting the OC on my GPU at the time, so seeing the mismatch after the others worked I figured it was from my meddling.

LaurV · 2011-12-13, 05:50

I finished another LL and decided to update the list in the first post. Meantime, nobody reported any new DC mismatch, or new first-time-LL done with CudaLucas, and I am not going to continuously ask. Later on, I may make a script to sniff into Primenet and grab all exponents that had at least one LL done with CudaLucas, I believe I know a way to do it. Anyhow, a manual check, found out two expos on the list cleared already (somebody did successfully DC's) and I stroke them out. If the lists will go longer in the future, the stroke-out lines will be deleted (it make no sense to have them anyhow, but just if someone wants to see that "we follow" :P)

moebius · 2011-12-13, 13:54

49190957

LaurV · 2011-12-20, 07:59

Quote:

Originally Posted by moebius

49190957

Added to the list. Seems like not so many people care about this list. Anyhow, the DC-bad-residue list is cleared now, as my exponent 26830123 was verified by Mr Kirrmaier and he got a residue that matched with MINE residue, and not with the former reported. I am quite happy about it.

Now, maybe the list with first-time-LL is not so important, and we hope that CudaLucas will change (to implement "scrambling") until it will come to re-test these exponents (1 year? two years? six months? more?).

But the DC-mismatches list is quite important (and not so "frequent" entries!) so I would take the opportunity to ask the people again to report their CudaLucas DC mismatches. We could avoid a lot of headache later.

LaurV · 2012-01-13, 04:10

Added a new CudaLucas DC mismatch for 26123989. Different of the former, when my residues were right (after triple checked by third parties) and the original tests were wrong, this time my test is already a triple check (!!!!) and it could highly be my residue which is wrong, because I kept roaming between v1.2b, v1.3(alpha) and v1.4.6 of CudaLucas, with both 4.0 and 3.2, and I also used built-cc2.1 on a board with 2.0 capability only (does it really matter? I could not find yet a build for cc2.0 on the CL thread, for the last 1.4.6, but I think the built for 2.1 should run on 2.0 without errors).

Strange exponent this 26123989...

edit: It was a "test case" where I tried to see which version is faster, and I also tried to overclock the Fermi chip a bit (about 7%, at 10% the image on the screen crashed, and at about 9% there were many errors displayed from cuFFT, but 7% OC seemed reliable....)

I just saw an anonymous grabbed the quadruple check. Eagerly waiting for his result...

kladner · 2012-01-13, 04:13

Quote:

Originally Posted by LaurV

Added to the list. Seems like not so many people care about this list. Anyhow, the DC-bad-residue list is cleared now, as my exponent 26830123 was verified by Mr Kirrmaier and he got a residue that matched with MINE residue, and not with the former reported. I am quite happy about it.

Now, maybe the list with first-time-LL is not so important, and we hope that CudaLucas will change (to implement "scrambling") until it will come to re-test these exponents (1 year? two years? six months? more?).

But the DC-mismatches list is quite important (and not so "frequent" entries!) so I would take the opportunity to ask the people again to report their CudaLucas DC mismatches. We could avoid a lot of headache later.

I respect this effort. It's just that I only run mfaktc on the GPU. But keep up the good work!

2011-12-02, 09:27	#2
moebius Jul 2009 Germany 11·61 Posts	For 25891057 the residue did match, but what about triple-checks? Last fiddled with by moebius on 2011-12-02 at 09:29

2011-12-02, 16:07	#5
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 3·23·149 Posts	You did not state it incorrectly, you put it very correctly. Prime95 will choose a random number k between 0 and p-1 and will rotate each residue inside of the p bits you have, with k bits. Then it will square the result. At the end you get the residue rotated with 2k bits. This ensure that the FFT deal with different data each time, so if there is a software bug in it, it would be almost impossible to produce the same result (unique up to a rotation) for the final residue. You can square a number x and take the result mod M, where M=2^p-1, to get x^2 (mod M). Now, if you square 2^kx, you get 2^(2k)x^2. But the order of 2 in M is p, because 2^p=1 (mod M), so you get in fact 2^(2k (mod p))x^2 (mod M), where the (mod p) is at the power, i.e. 2k is taken (mod p). Now if you note that x=y (mod M) means x=aM+y, you can write x=a(M+1)-a+y. Think at that like modulo M+1, which is 2^p, this means you can find y by adding the last p bits of x with the other bits of x. This is in fact a rotation of x^2 with 2k bits. Example: for p=13, M=8191, the "standard" test gives the series of residues: 4,14,194,4870,3953,5970,1857,36,1294,3470,128,0 If you shift the initial value with 1 bit to the left (k=1) what you get is 8,56,3104,1688,7051,5294,5024,9,7248,4557,16,0 In this case the number is prime, and the residue is always 0. For p=11, M=2047, the "standard" tests gives 4,14,194,788,701,119,1877,240,282,1736 and the "rotated by k=1" test gives 8,56,1057,1122,1962,1083,981,15,209,566 If you look to the binary representations of the two final residues, they are "the same up to a rotation with 5 positions". Where does 5 come from, you can compute, and indeed, if you rotate the second result 5 positions to the left, you get the first. 1736 = binary 110 1100 1000 0566 = binary 010 0011 0110 So, P95 goes through all this trouble for each term in the LL sequence of residues, to ensure that FFT squaring deals with different data each time when you LL or DC. CudaLucas does not. It always starts with 4, square it, subtract 2, square it, subtract 2, etc. A bug (or overflow, or whatever) in the FFT code will produce always the same error in the "square it" step. Therefore always the same (wrong) residue. Prime95 can produce a number of p different residues (internally), if you run it so many times for the same exponent, because it will pick a (different) random k each time. The residues have to match after P95 rotates them with the right number of bits, and communicate them to you. Last fiddled with by LaurV on 2011-12-13 at 05:41

2011-12-13, 13:54	#8
moebius Jul 2009 Germany 11×61 Posts	update 49190957

2012-01-13, 04:10	#10
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 3×23×149 Posts	Added a new CudaLucas DC mismatch for 26123989. Different of the former, when my residues were right (after triple checked by third parties) and the original tests were wrong, this time my test is already a triple check (!!!!) and it could highly be my residue which is wrong, because I kept roaming between v1.2b, v1.3(alpha) and v1.4.6 of CudaLucas, with both 4.0 and 3.2, and I also used built-cc2.1 on a board with 2.0 capability only (does it really matter? I could not find yet a build for cc2.0 on the CL thread, for the last 1.4.6, but I think the built for 2.1 should run on 2.0 without errors). Strange exponent this 26123989... edit: It was a "test case" where I tried to see which version is faster, and I also tried to overclock the Fermi chip a bit (about 7%, at 10% the image on the screen crashed, and at about 9% there were many errors displayed from cuFFT, but 7% OC seemed reliable....) I just saw an anonymous grabbed the quadruple check. Eagerly waiting for his result... Last fiddled with by LaurV on 2012-01-13 at 04:22

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Prime95 vs. CUDALucas	storm5510	Software	10	2022-04-18 05:11
CudaLucas Residual	evoflash	GPU Computing	21	2017-11-13 12:04
CUDALucas gives all-zero residues	fivemack	GPU Computing	4	2016-07-21 15:49
settings for cudaLucas	fairsky	GPU Computing	11	2013-11-03 02:08
Trying to run CUDALucas on Windows 8 CP	Rodrigo	GPU Computing	12	2012-03-07 23:20

2011-12-02, 09:58	#3
ET_ Banned "Luigi" Aug 2002 Team Italia 3×1,619 Posts	I had different behaviors with CUDALucas. Some tests ended with a correct residue, some didn't. As it is fairly hard that 2 numbers end up with the same wrong residue, I suppose that CUDALucas is not that bad. Luigi

2011-12-02, 16:15	#6
bcp19 Oct 2011 7·97 Posts	I know I ran a few DC on my GPU prior to GPUto72 and had 1 mismatch, but I had been adjusting the OC on my GPU at the time, so seeing the mismatch after the others worked I figured it was from my meddling.

2011-12-13, 05:50	#7
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2829₁₆ Posts	I finished another LL and decided to update the list in the first post. Meantime, nobody reported any new DC mismatch, or new first-time-LL done with CudaLucas, and I am not going to continuously ask. Later on, I may make a script to sniff into Primenet and grab all exponents that had at least one LL done with CudaLucas, I believe I know a way to do it. Anyhow, a manual check, found out two expos on the list cleared already (somebody did successfully DC's) and I stroke them out. If the lists will go longer in the future, the stroke-out lines will be deleted (it make no sense to have them anyhow, but just if someone wants to see that "we follow" :P)