20210926, 22:17  #12  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
5,783 Posts 
Quote:
Quote:
y=a x + c = 194; a=64, x=3, c=2 M=(194 + 64 * 3) / 2 = 193 or M = (y+ax)/c = (ax+c + ax) /c = 2ax/c + 1. Following your formula M must be odd because a is a power of 2 > 1. Do your algebra. There's a serious evaluation error in your M_Value that hides whether your method works or not, or what it is, or a serious error in the formula preceding its evaluation. I count 11 operations per iteration, versus 3 in the usual LL. Hard to imagine that 11 is faster than 3. Mods: is it time to move this thread to misc math yet? Last fiddled with by kriesel on 20210926 at 22:29 

20210926, 22:25  #13  
Apr 2019
17 Posts 
Quote:


20210926, 22:48  #14 
Apr 2020
499 Posts 
You've come up with an incredibly convoluted way of reducing numbers modulo 2^n1. There is, of course, a much faster way, and indeed this calculation can be done very quickly on a computer because they work in binary.
For example, let's suppose we would like to calculate 37634 mod 2^131. That is, we want to write 37634 = q(2^131) + r, and we are interested in the value of r. But this is equivalent to 37634 = q*2^13 + (rq), so we can very easily find q and rq by writing 37634 in binary, and then add them together to get r: Code:
1001001100000010 _____________ last 13 bits q = 100 rq = 1001100000010 r = 1001100000110 If the value of r that we get is still larger than the initial modulus (because adding q to rq added an extra bit at the front, or because we started with a number larger than ~the square of the modulus), then we just repeat the process. Last fiddled with by charybdis on 20210926 at 22:53 
20210927, 14:30  #15  
Apr 2019
21_{8} Posts 
Quote:
I made a few corrections here, P13 =8191 37634=194^22 Y=194 a=2^((p1)/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^21)/2 =4 add to M_value M_value=772+4=776 Add a^2 to M_value 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 =2888 add to M_value M_value=58404+2888=61292 //for even numbers skip this part Add a^2 to M_value 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 

20210927, 14:48  #16  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
5,783 Posts 
Quote:
(Isn't p13 standard nomenclature for a 13digit prime? M13 is for 2^{13}1, which is a p4) See https://www.mersenneforum.org/showpo...41&postcount=3 and https://www.mersenneforum.org/showpo...72&postcount=9 Last fiddled with by kriesel on 20210927 at 15:05 

20210927, 14:57  #17 
Apr 2019
17_{10} Posts 

20210927, 14:59  #18 
Apr 2020
499 Posts 
Apologies, yes you have got the squaring in there too. But you're still reinventing the wheel. Let's look at what's actually happening here.
194 = 64*3 + 2, so we know 194^2 = 64^2*3^2 + 2*64*3*2 + 2^2. You've noticed that the first term can be easily reduced mod 2*64^21 (this is where the (3^21)/2 comes from), and that the last two terms can be rewritten as 64*3*2 + 64*3*2 + 2^2 = 2(64*3 + 194). This idea of "splitting the number into pieces" when multiplying two numbers is the basis of long multiplication, and faster algorithms such as Karatsuba and ToomCook. GIMPS uses FFTs for multiplication, which are much faster for the enormous numbers involved. Nothing new here. Multiplication algorithms have been a major subject of research for decades. Newbies aren't going to make breakthroughs. 
20210927, 16:01  #19  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
5783_{10} Posts 
Quote:
Quote:
After several followup posts, what "this" is is still unclearly stated. For contrast, consider the style of the LucasLehmer section of https://www.mersenne.org/various/math.php There, in simple smalloperands form, an iteration is 3 operations: square, subtract two, mod Mp. Most of the time is spent in the squaring. I counted 11 operations per iteration in what I think the OP is trying to describe. Still waiting on: Quote:
Quote:
Quote:
Note that it is of little future interest in any event, since GIMPS will rarely be doing LL in the future; some DC will still occur for a while, but new primality firsttest assignments are given as PRP only, because of the number theory supporting tremendously higher reliability, and other theory supporting verification at a >2:1 overall test speed advantage over LL, DC, TC, etc. Eventually LL will only be done to verify a rare new prime discovery after a PRP test passes verification and returns "probably prime" instead of the almost always result "composite". So that will lead to GIMPS PRP results many times daily, and LL on one exponent or none during some years. If tomorrow, a means of reducing LL compute time by half, and PRP time by 10% were found, programming effort would focus on the 10% PRP improvement, which would speed the GIMPS project throughput by nearly 10%, while the LL change would only make LL & DC etc roughly comparable (still a little slower) than PRP/GEC/proof as it is now. Quote:
Quote:
Last fiddled with by kriesel on 20210927 at 16:24 

20210927, 16:18  #20 
Romulan Interpreter
Jun 2011
Thailand
2^{4}·13·47 Posts 
Moved to misc math, renamed properly.
