 mersenneforum.org Hi... trying something not new.
 Register FAQ Search Today's Posts Mark Forums Read  2021-09-24, 10:09 #1 Lan   Apr 2019 100012 Posts Hi... trying something not new. Hi... can someone help me test this? Let say you want to verify a number whether it's prime or not. For example 2^7-1=127. Rearrange the number so it looks like this, 2*(8^2)-1 From the 3rd sequence you have 194(closest to our number) and you rearrange the number to get, 14^2-2 You will get two squares numbers 14 and 8. Divide 14 with 8 and will get 6 as the reminder, 8*1+6=14 From this equation 8*1+6=14, 8 is the base number, 1 is the multiplier and 6 is the reminder. You can set the number by using variable in case you could not see it like AB+C=D or whatever. add 14 to 8 and then multiply 6 then you will get 132. Skip this part and go to the multiplier. Square the multiplier. From the equation it's 1 so you will still get 1. After that plus 1. So in case u don't get it, if the multiplier for example is 7,you square that 7 then u will get 49. After getting 49, you add 1 so get 50. Ok now back to 1. After adding 1 for your multiplier, divide it with 2 so 2/2 is still 1. Now back to 132, add the answer and minus (base number^2) from 132, 132+1-64=69 Minus the last result with 2. U will get final result, 67. //just in case u have the final result larger than 127(while running your iteration) What you need to do is just divide the number with 127 and then the reminder will Be the new final number. I had been testing the iteration and it seemed that the final Numbers were always smaller than the test number.(maybe because I hadn't test it With big enough numbers.) Repeat this iteration for 7-1=6 //If u can barely read it, I am sorry.. I used phone to post this thread. Please help me test this thank you... Last fiddled with by Lan on 2021-09-24 at 10:13   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.   Thread Tools Show Printable Version Email this Page

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