mersenneforum.org left shifted S0 value
 Register FAQ Search Today's Posts Mark Forums Read

2012-07-26, 03:42   #1
ATH
Einyen

Dec 2003
Denmark

7·449 Posts
left shifted S0 value

From the math page: http://www.mersenne.org/various/math.php

Quote:
 GIMPS double-checking goes a bit further to guard against programming errors. Prior to starting the Lucas-Lehmer test, the S0 value is left-shifted by a random amount. Each squaring just doubles how much we have shifted the S value.
How is these left-shifted residues converted back? Doesn't the -2 step each iteration ruin an easy conversion?

2012-07-26, 04:17   #2
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts

Quote:
 Originally Posted by ATH From the math page: http://www.mersenne.org/various/math.php How is these left-shifted residues converted back? Doesn't the -2 step each iteration ruin an easy conversion?
230 in binary:

11100110

230 in binary left-shifted 2 bits:

10011011

Now the third bit is the units bit, instead of the first.

228 in binary:

11100100

228 left shifted two bits:

10010011

230-2=228 in two-left-shift binary:

10011011 -- 230 two-left-shifted
00001000 -- 2 two-left-shifted
10010011 -- which is 228 left-shifted two bits

Last fiddled with by Dubslow on 2012-07-26 at 04:18 Reason: s/shit/shift (unfortunately, i'm not joking)

2012-07-26, 04:44   #3
LaurV
Romulan Interpreter

Jun 2011
Thailand

23×1,193 Posts

Quote:
 Originally Posted by ATH Doesn't the -2 step each iteration ruin an easy conversion?
See the posts #4, #5 and #16, 17, 18 in the "don't DC them..." thread.

2012-07-26, 05:55   #4
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

24F916 Posts

Quote:
 Originally Posted by ATH From the math page: http://www.mersenne.org/various/math.php How are these left-shifted residues converted back? Doesn't the -2 step each iteration ruin an easy conversion?
-2 is shifted appropriately. Shift doubles with each squaring (and wraps around). The interim RES64 residues are "backshifted" (or cut out from the properly offsetted place) so that they are directly comparable between runs. The savefiles are raw complete residues (not "backshifted"), but can be compared (given that the Mp is the same and iteration is the same); one of the state values (recorded in the savefile) is the current shift. This is all easily readable from the P95 source.

Last fiddled with by Batalov on 2012-07-26 at 06:02 Reason: shifted <-> backshifted

2012-07-26, 14:35   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Batalov -2 is shifted appropriately. Shift doubles with each squaring (and wraps around). The interim RES64 residues are "backshifted" (or cut out from the properly offsetted place) so that they are directly comparable between runs. The savefiles are raw complete residues (not "backshifted"), but can be compared (given that the Mp is the same and iteration is the same); one of the state values (recorded in the savefile) is the current shift. This is all easily readable from the P95 source.
so basically:

Code:
(11:32)>k=3;d=4<<k;for(x=1,4,d=d^2-2*(2^(2^x*k));print(d>>(2^x*k)","))
14,
194,
37634,
1416317954,
showing what to shift it back. the difference here being we don't have the mod operation of a p for an exponent.

Last fiddled with by science_man_88 on 2012-07-26 at 14:38

 2012-07-26, 14:59 #6 ATH Einyen     Dec 2003 Denmark C4716 Posts Ok, so this only works for left or right shifted S0 values I guess. I was wondering if it was possible to find the penultimate LL step ( http://www.mersenneforum.org/showthread.php?t=5862 ) for the 2 other "universel" initial values s0=10 and s0=2/3 without running all the tests again. I calculated up to M33 with GMP library but the high ones would take years and years that way: penultimatellstep.txt It seems neither Prime95/mprime, Mlucas or Glucas can run LL test with s0=10 or s0=2/3. Last fiddled with by ATH on 2012-07-26 at 15:11
 2012-07-26, 17:28 #7 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100100111110012 Posts You can fairly easily rebuild a slightly modified Prime95 (on either win or lin) and then each test would be as long as the conventional (4<
2012-07-27, 01:27   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 Originally Posted by ATH Ok, so this only works for left or right shifted S0 values I guess. I was wondering if it was possible to find the penultimate LL step ( http://www.mersenneforum.org/showthread.php?t=5862 ) for the 2 other "universel" initial values s0=10 and s0=2/3 without running all the tests again. I calculated up to M33 with GMP library but the high ones would take years and years that way: penultimatellstep.txt It seems neither Prime95/mprime, Mlucas or Glucas can run LL test with s0=10 or s0=2/3.

2012-07-27, 02:16   #9
ATH
Einyen

Dec 2003
Denmark

1100010001112 Posts

Quote:
 Originally Posted by science_man_88 http://www.mersenneforum.org/showthread.php?t=138 also showed up when I was searching on google.
Cool, I forgot that thread and that there was infinitely many "universal" seeds, I thought most of them depended on p.

Quote:
 Originally Posted by Batalov You can fairly easily rebuild a slightly modified Prime95 (on either win or lin) and then each test would be as long as the conventional (4<
I'll try that tomorrow, but I never compiled Prime95 before. Do you know if its possible in msys+mingw for windows?

 2012-07-27, 02:24 #10 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 223718 Posts On Windows, I had built with VC++; I don't remember if I tried mingw. Once you build the vanilla binary, then you will be set for a life of experimentation. When I built it, I was getting around the built-in PRP base (was 3; now a parameter) for testing GFN'(3)s; with base 3 there were all PRPs . AFAIR, (32[sup]n[/sup]+1)/2 for n=24 and 25 were also composite, but W.K. didn't post them (I think he waits for double-checks with other software). ...this reminds me that this could be fun to DC with geneferCUDA (slightly modified if needed: for the divisor of 2; why don't I play with that over this weekend? :knuckle-flexing-smiley-needed:) Last fiddled with by Batalov on 2012-07-27 at 02:40
2012-07-27, 03:57   #11

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

Quote:
 Originally Posted by ATH How is these left-shifted residues converted back? Doesn't the -2 step each iteration ruin an easy conversion?
I had exactly the same blind spot: not realizing that the -2 would be shifted the same amount as the S values.

 Similar Threads Thread Thread Starter Forum Replies Last Post Flatlander Science & Technology 3 2011-09-22 11:19 Mini-Geek No Prime Left Behind 52 2011-09-12 06:27 ATH PrimeNet 11 2010-06-03 06:38 petrw1 PrimeNet 311 2010-04-06 05:18 gd_barnes Lounge 0 2008-01-21 09:05

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

Sun Jun 20 18:19:48 UTC 2021 up 23 days, 16:07, 0 users, load averages: 1.74, 1.51, 1.55