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×419 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

1C3516 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

2·11·397 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

53·73 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 7·419 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 100011101001012 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

26·131 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

7×419 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 53×73 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 06:56.

Mon Sep 21 06:56:07 UTC 2020 up 11 days, 4:07, 0 users, load averages: 1.40, 1.55, 1.49