Torture and Benchmarking test of Prome95.Doubts in implementation

[Dubslow]

Originally Posted by science_man_88

(11:09)>lucaslehmer2(p)=s=Mod(8,2^p-1);for(x=1,p-3,s=s^2-2;print(s));if(s==0,1,0)
%35 = (p)->s=Mod(8,2^p-1);for(x=1,p-3,s=s^2-2;print(s));if(s==0,1,0)
(11:09)>lucaslehmer2(13)
Mod(62, 8191)
Mod(3842, 8191)
Mod(780, 8191)
Mod(2264, 8191)
Mod(6319, 8191)
Mod(6825, 8191)
Mod(6597, 8191)
Mod(1624, 8191)
Mod(8063, 8191)
Mod(0, 8191)

is what I get.

See first answer to OP's most recent questions. LaurV somehow got 56 on the first iteration, and 31xx on the second.

[science_man_88]

Originally Posted by Dubslow

See first answer to OP's most recent questions. LaurV somehow got 56 on the first iteration, and 31xx on the second.

I did look no constant difference from the square. I made one that can use any power of 2 the problem not all powers of 2 will find the same answer by my slightly altered method ( for 2^f as a start go until p-f ( which also fits the original) but the reason I switched to this is because I don't know fft and -2 only seemed to work for 8 if I did p-3 in the loop. But I see the flaw.

[cheesehead]

Originally Posted by Dubslow

I don't think so, because based on LaurV's post that I linked, the standard square-and-subtract doesn't apply.

Sure, it applies. I think LaurV made a mistake in going from 8 to 56 instead of to 62.

[Dubslow]

But he got 0 as the correct residue, whereas if you do it our way you get a non-zero residue, despite the fact that it's prime.

[cheesehead]

Originally Posted by Dubslow

I don't think so, because based on LaurV's post that I linked, the standard square-and-subtract doesn't apply.

Of course it applies. If the second run used a different algorithm than the first run's square-and-subtract, then the second run couldn't serve as a double-check on the first run's result because it wouldn't be performing the correct Lucas-Lehmer algorithm.

I don't see how he did his first iteration there.

I've posted a query in that thread.

[science_man_88]

Originally Posted by Dubslow

But he got 0 as the correct residue, whereas if you do it our way you get a non-zero residue, despite the fact that it's prime.

I got a 0 residue a few post back but I didn't do it normally so I'll have to prove it works.

[cheesehead]

Originally Posted by Dubslow

But he got 0 as the correct residue, whereas if you do it our way you get a non-zero residue, despite the fact that it's prime.

Actually, "our" way gets a zero residue, too ... but it gets it one iteration too early, which is a discrepancy I haven't yet figured out. For now, I'm waiting for someone else to figure out what I/we have missed.

[science_man_88]

Originally Posted by cheesehead

Actually, "our" way gets a zero residue, too ... but it gets it one iteration too early, which is a discrepancy I haven't yet figured out. For now, I'm waiting for someone else to figure out what I/we have missed.

forprime(r=1,200,for(e=1,r-1,print1(lucaslehmer2(r,e)));print(","r))

is the code I made to try and learn more.

0,2
01,3
0100,5
010000,7
0000000000,11
011100000000,13
0100000000000000,17
010100010000000000,19
0000000000000000000000,23
0000000000000000000000000000,29
010100000000000000000000000000,31
000000000000000000000000000000000000,37
0000000000000000000000000000000000000000,41
000000000000000000000000000000000000000000,43
0000000000000000000000000000000000000000000000,47
0000000000000000000000000000000000000000000000000000,53
0000000000000000000000000000000000000000000000000000000000,59
011101000000000000000000000000000000000000000000000000000000,61
000000000000000000000000000000000000000000000000000000000000000000,67
0000000000000000000000000000000000000000000000000000000000000000000000,71
000000000000000000000000000000000000000000000000000000000000000000000000,73
000000000000000000000000000000000000000000000000000000000000000000000000000000,79
0000000000000000000000000000000000000000000000000000000000000000000000000000000000,83
0110000000000000000000000000000000000000000000000000000000000000000000000000000000000000,89
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,97
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,101
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,103
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,107
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,109
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,113
010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,127
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,131
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,137
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,139
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,149
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,151
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,157
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,163
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,167
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,173
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,179
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,181
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,191
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,193
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,197
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,199

[science_man_88]

they responded to you I think I get what they mean.

[cheesehead]

patrik has explained:

Originally Posted by patrik

The -2 has to be rotated to the appropriate place. With 8 rotated one bit, its square will be rotated two bits, so you have to take 8^2-2*2^2.

So that's what I overlooked -- shifting the 2 that's subtracted.

[paramveer]

Thanks for making clear about Double checking and torture issue.