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

2021-09-26, 22:17   #12
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

5,783 Posts

Quote:
 Originally Posted by Lan Most of the time, people want to see the program output themselves rather than just its report.
Round these parts, people want to see code, number theoretic basis, efficiency, and accurate results.
Quote:
 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
193, a 4:1 discrepancy.

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 2021-09-26 at 22:29

2021-09-26, 22:25   #13
Lan

Apr 2019

1710 Posts

Quote:
 Originally Posted by kriesel Round these parts, people want to see code, number theoretic basis, efficiency, and accurate results. 193, a 4:1 discrepancy. 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. Mods: is it time to move this thread to misc math yet?
My mistake... that was actually M = (y+ ax)* c . Please recheck it again. I am sorry.

 2021-09-26, 22:48 #14 charybdis     Apr 2020 22·53 Posts You've come up with an incredibly convoluted way of reducing numbers modulo 2^n-1. 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^13-1. That is, we want to write 37634 = q(2^13-1) + r, and we are interested in the value of r. But this is equivalent to 37634 = q*2^13 + (r-q), so we can very easily find q and r-q by writing 37634 in binary, and then add them together to get r: Code: 1001001100000010 _____________ last 13 bits q = 100 r-q = 1001100000010 r = 1001100000110 Converting back into decimal, we get r = 4870. If the value of r that we get is still larger than the initial modulus (because adding q to r-q 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 2021-09-26 at 22:53
2021-09-27, 14:30   #15
Lan

Apr 2019

218 Posts

Quote:
 Originally Posted by charybdis You've come up with an incredibly convoluted way of reducing numbers modulo 2^n-1. 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^13-1. That is, we want to write 37634 = q(2^13-1) + r, and we are interested in the value of r. But this is equivalent to 37634 = q*2^13 + (r-q), so we can very easily find q and r-q by writing 37634 in binary, and then add them together to get r: Code: 1001001100000010 _____________ last 13 bits q = 100 r-q = 1001100000010 r = 1001100000110 Converting back into decimal, we get r = 4870. If the value of r that we get is still larger than the initial modulus (because adding q to r-q 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.
No it's not. The initial value starts with 194, not 37634. Please evaluate the method thoroughly.

I made a few corrections here,

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

2021-09-27, 14:48   #16
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

5,783 Posts

Quote:
 Originally Posted by Lan P13 =8191 37634=194^2-2 Y=194 ... Subtract 2 from M_value M_value=4870 Check if divisible by p13 No Move M_value, y; ... Check if divisible by p13 yes M_value=61290%8191 <== M_value=3953 Move M_value, y;
What do you mean by "is divisible by"? M>=Mp? In large-exponent space, M<Mp is so rare, efficient code does not bother to test interim residues for that.

(Isn't p13 standard nomenclature for a 13-digit prime?

M13 is for 213-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 2021-09-27 at 15:05

2021-09-27, 14:57   #17
Lan

Apr 2019

17 Posts

Quote:
 Originally Posted by kriesel What do you mean by "is divisible by"? M>=Mp? (Isn't p13 standard nomenclature for a 13-digit prime? M13 is for 213-1, which is a p4)
Okkey... I agree. It's M13.

 2021-09-27, 14:59 #18 charybdis     Apr 2020 50010 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^2-1 (this is where the (3^2-1)/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 Toom-Cook. 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.
2021-09-27, 16:01   #19
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

5,783 Posts

Quote:
 Originally Posted by Lan Hi... can someone help me test this? Let say you want to verify a number whether it's prime or not.
What follows in that post is about as incoherent a description of an algorithm as I've ever seen. And its purpose is pretty darn vague and overly general too. It's missing any mention of "Mersenne".
Quote:
 You will get two squares numbers 14 and 8.
Neither are squares.
After several followup posts, what "this" is is still unclearly stated.
For contrast, consider the style of the Lucas-Lehmer section of https://www.mersenne.org/various/math.php
There, in simple small-operands 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:
 Originally Posted by kriesel What do you mean by "is divisible by"?
Quote:
 Originally Posted by kriesel Round these parts, people want to see code, number theoretic basis, efficiency, and accurate results.
Quote:
 Originally Posted by kriesel 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.
Quote:
 Originally Posted by Lan Is there anyone who can comfirm the speed difference between using standard LL test and the test above.
A rough estimate of the most efficient possible implementation of the method somewhat described in this thread is that it would be less than 1/3 as efficient as conventional LL, so <1/6 PRP/GEC/proof. In other words more than 3 or 6 times slower. (And that assumes a world class skill level at using IBDWT for the multi-million-computer-word operands where beneficial. The top programmers will not waste their time on it.)
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 first-test 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:
 Should I provide a full calculations instead? Do you want me to write solutions for p13,17 and 19?
no x 4.
Quote:
 Originally Posted by kriesel Do your algebra. Mods: is it time to move this thread to misc math yet?
Lan: who are you, how old are you, what is your math & programming background? Native language? What you've posted in this thread so far seems to me consistent with a very limited understanding of the topic. There are plenty of resources available to learn more. Use the forum's search function, the reference info, especially how fast can we multiply, the recommended books thread, or a good library.

Last fiddled with by kriesel on 2021-09-27 at 16:24

 2021-09-27, 16:18 #20 LaurV Romulan Interpreter     Jun 2011 Thailand 22·3·5·163 Posts Moved to misc math, renamed properly.

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

Thu Oct 21 13:11:03 UTC 2021 up 90 days, 7:40, 1 user, load averages: 1.38, 1.37, 1.34