mersenneforum.org Hi... trying something not new.
 Register FAQ Search Today's Posts Mark Forums Read

 2021-09-24, 14:01 #2 Viliam Furik     "Viliam Furík" Jul 2018 Martin, Slovakia 10111010012 Posts 14^2-2 = 127 + 67 == 67 (mod 127). You have (probably - maybe coincidentally) computed the next iteration of the LL test.
2021-09-24, 15:03   #3
Lan

Apr 2019

17 Posts

Quote:
 Originally Posted by Viliam Furik 14^2-2 = 127 + 67 == 67 (mod 127). You have (probably - maybe coincidentally) computed the next iteration of the LL test.
That's what I mean by introducing this calculation. It can be substituted as a part of the original iterations.

 2021-09-25, 17:07 #4 Lan   Apr 2019 17 Posts Is there anyone who can comfirm the speed difference between using standard LL test and the test above. I mean comparing between 194/mod127 with the solution given Should I provide a full calculations instead? Do you want me to write solutions for p13,17 and 19?
2021-09-25, 18:15   #5
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

1023310 Posts

Quote:
 Originally Posted by Lan Is there anyone who can comfirm the speed difference between using standard LL test and the test above.
Unless it is double the speed, it does not make a difference (for MPrimes). Using PRP and the proof files we are almost double the speed of a LL test and a DC.

2021-09-25, 18:32   #6
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×11×277 Posts

Quote:
 Originally Posted by Uncwilly Unless it is demonstrably more than double the speed, it does not make a difference (for MPrimes). Using PRP and the proof files we are almostmore than double the speed of a LL test and a DC & occasional TC, 4th, etc.
(FTFY)
PRP+proof ~1.01 test effort and high certainty of correctness.
LL & LL DC & ~4% LL TC ~2.04 test effort at wavefront. 2.04/1.01 >2. And PRP/GEC/proof gets more advantageous at higher exponent, since error rate & LLTC, 4thLL, etc cost goes up with run time. And uncorrected error is found empirically to be ~2%/LLtest, but only ~24ppm for PRP.
The OP appears to be a long way of performing an LL iteration. Lots of steps described = lots of chance for error.

Last fiddled with by kriesel on 2021-09-25 at 18:39

2021-09-25, 20:40   #7
Lan

Apr 2019

17 Posts

Quote:
 Originally Posted by Uncwilly Unless it is double the speed, it does not make a difference (for MPrimes). Using PRP and the proof files we are almost double the speed of a LL test and a DC.
Quote:
 Originally Posted by kriesel (FTFY) PRP+proof ~1.01 test effort and high certainty of correctness. LL & LL DC & ~4% LL TC ~2.04 test effort at wavefront. 2.04/1.01 >2. And PRP/GEC/proof gets more advantageous at higher exponent, since error rate & LLTC, 4thLL, etc cost goes up with run time. And uncorrected error is found empirically to be ~2%/LLtest, but only ~24ppm for PRP. The OP appears to be a long way of performing an LL iteration. Lots of steps described = lots of chance for error.
Thanks to both of you for replying. Actually those tests are quite similar, though prp test has few operations involved.
(That explains why it's much faster).Even if involving more operations in one iteration will lead to errors but what I request is compare the speed of my test with the LL test ( or perhaps prp test too). I want a speed report. Thats all.

Anyway if you want me to write full calculations as an example, I will proceed.

 2021-09-25, 21:18 #8 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22·32·61 Posts You can use the LL-Test codes below to compare with your own code. PARI-GP would probably be the most practical. http://www.rosettacode.org/wiki/Lucas-Lehmer_test Please let us know how your code compares.
2021-09-25, 22:40   #9
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×11×277 Posts

Quote:
 Originally Posted by Lan Actually those tests are quite similar, though prp test has few operations involved. (That explains why it's much faster).
PRP is fast in large part because we only need to do it once per exponent. The VDF based proof generation allows verification of correct completion for additional effort that's a fraction of a percent of a first test or of a second test.
LL: start with seed 4. Square it, subtract 2 (which is almost free when done as part of carry propagation), mod Mp, p-2 times.
Best available large-number squaring algorithm is used for both in the usual GIMPS software.

Describe your method in exponent-as-a-parameter terms for exponent ~100,000,000, for comparison with the above. In algebraic form, not worked numeric trivially-small-exponent examples.
Describe what error detection and recovery methods you would incorporate in your sequence to ensure high probability of correct completion of ~100,000,000+ iterations on 100,000,000+ bit length operands.
Explain how scaling (proportionality constants or order) for your method is superior to what's described in https://www.mersenneforum.org/showpo...65&postcount=3 and elsewhere.

Last fiddled with by kriesel on 2021-09-25 at 22:41

2021-09-26, 20:57   #10
Lan

Apr 2019

218 Posts

Quote:
 Originally Posted by a1call You can use the LL-Test codes below to compare with your own code. PARI-GP would probably be the most practical. http://www.rosettacode.org/wiki/Lucas-Lehmer_test Please let us know how your code compares.

Most of the time, people want to see the program output themselves rather than just its report. It's best for you to try I suggest, see the output with your own eyes. Here the complete calculations for p13.

Edited
I am sorry... I still don't have access to the main computer. I couldn't attach the document so I wrote it manually but I think you will get the point.

P13 =8191
37634=194^2-2
Y=194

a=2^((p-1)/2) p=13
a=2^6 a^2=2^12

Y=ax+c
194=64(3)+2

M_value=(y+ax)/c
M_value=772

x=3, x is odd
//if odd, after squaring, subtract 1 before
//dividing with 2

(3^2-1)/2
M_value=772+4=776

M_value=4096+776
M_value=4872

Subtract 2 from M_value
M_value=4870

Check if divisible by p13
No

Move M_value, y;

Y=ax+c
4870=64(76)+6

M_value=(y+ax)/c
M_value=58404

x=76, x is even
//if even, You don't have to -1
(76^2)/2
M_value=58404+2888=61292

//for even numbers skip this part
M_value=
M_value=

Subtract 2 from M_value
M_value=61290

Check if divisible by p13
yes
M_value=61290/8191
M_value=3953

Move M_value, y;

//The rest of the calculations are the same

If you want to try on PRP test. Just substitute y with 3
(Check if divisible) and skip subtracting 2 at the end
but !!! Don't Substitute with squared number !!!
Just simply input 3, not 3^2. For example, if you substitute y
with 81^2 for p7, you won't get 84 at the end.
I hope you will give it a try.

2021-09-26, 21:06   #11
Lan

Apr 2019

17 Posts

Quote:
 Originally Posted by kriesel PRP is fast in large part because we only need to do it once per exponent. The VDF based proof generation allows verification of correct completion for additional effort that's a fraction of a percent of a first test or of a second test. PRP: start with seed 3. Square it mod Mp, p-1 times. LL: start with seed 4. Square it, subtract 2 (which is almost free when done as part of carry propagation), mod Mp, p-2 times. Best available large-number squaring algorithm is used for both in the usual GIMPS software. Describe your method in exponent-as-a-parameter terms for exponent ~100,000,000, for comparison with the above. In algebraic form, not worked numeric trivially-small-exponent examples. Describe what error detection and recovery methods you would incorporate in your sequence to ensure high probability of correct completion of ~100,000,000+ iterations on 100,000,000+ bit length operands. Explain how scaling (proportionality constants or order) for your method is superior to what's described in https://www.mersenneforum.org/showpo...65&postcount=3 and elsewhere.
I will try... but I can't guarantee since I don't have access to the main computer (yet).
Nevertheless, you can try coding my calculations and see the result yourself.

All times are UTC. The time now is 11:04.

Wed Jan 19 11:04:22 UTC 2022 up 180 days, 5:33, 0 users, load averages: 2.57, 2.04, 1.73