mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-07-26, 03:42   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

22×3×241 Posts
Default 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?
ATH is offline   Reply With Quote
Old 2012-07-26, 04:17   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by ATH View Post
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)
Dubslow is offline   Reply With Quote
Old 2012-07-26, 04:44   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

21BB16 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
LaurV is offline   Reply With Quote
Old 2012-07-26, 05:55   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

237E16 Posts
Default

Quote:
Originally Posted by ATH View Post
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
Batalov is offline   Reply With Quote
Old 2012-07-26, 14:35   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by Batalov View Post
-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
science_man_88 is offline   Reply With Quote
Old 2012-07-26, 14:59   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

22·3·241 Posts
Default

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
ATH is offline   Reply With Quote
Old 2012-07-26, 17:28   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·7·11·59 Posts
Default

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<<s) tests.
Batalov is offline   Reply With Quote
Old 2012-07-27, 01:27   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
http://www.mersenneforum.org/showthread.php?t=138 also showed up when I was searching on google.
science_man_88 is offline   Reply With Quote
Old 2012-07-27, 02:16   #9
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

22·3·241 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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 View Post
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<<s) tests.
I'll try that tomorrow, but I never compiled Prime95 before. Do you know if its possible in msys+mingw for windows?
ATH is offline   Reply With Quote
Old 2012-07-27, 02:24   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×7×11×59 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2012-07-27, 03:57   #11
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Nothing left to discover? Flatlander Science & Technology 3 2011-09-22 11:19
no twin left behind? Mini-Geek No Prime Left Behind 52 2011-09-12 06:27
Doublecheck always have shifted S0 value? ATH PrimeNet 11 2010-06-03 06:38
Less than 10,000 left.... petrw1 PrimeNet 311 2010-04-06 05:18
New 'No Prime Left Behind' project gd_barnes Lounge 0 2008-01-21 09:05

All times are UTC. The time now is 08:46.

Thu Aug 13 08:46:06 UTC 2020 up 5:21, 0 users, load averages: 2.35, 2.08, 1.94

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