mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-09-26, 22:17   #12
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

3×1,933 Posts
Default

Quote:
Originally Posted by Lan View Post
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
kriesel is online now   Reply With Quote
Old 2021-09-26, 22:25   #13
Lan
 
Apr 2019

17 Posts
Default

Quote:
Originally Posted by kriesel View Post
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.
Lan is offline   Reply With Quote
Old 2021-09-26, 22:48   #14
charybdis
 
charybdis's Avatar
 
Apr 2020

2×251 Posts
Default

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
charybdis is offline   Reply With Quote
Old 2021-09-27, 14:30   #15
Lan
 
Apr 2019

17 Posts
Default

Quote:
Originally Posted by charybdis View Post
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
=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
Lan is offline   Reply With Quote
Old 2021-09-27, 14:48   #16
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

3×1,933 Posts
Default

Quote:
Originally Posted by Lan View Post
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
kriesel is online now   Reply With Quote
Old 2021-09-27, 14:57   #17
Lan
 
Apr 2019

218 Posts
Default

Quote:
Originally Posted by kriesel View Post
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.
Lan is offline   Reply With Quote
Old 2021-09-27, 14:59   #18
charybdis
 
charybdis's Avatar
 
Apr 2020

2·251 Posts
Default

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.
charybdis is offline   Reply With Quote
Old 2021-09-27, 16:01   #19
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

3·1,933 Posts
Default

Quote:
Originally Posted by Lan View Post
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 View Post
What do you mean by "is divisible by"?
Quote:
Originally Posted by kriesel View Post
Round these parts, people want to see code, number theoretic basis, efficiency, and accurate results.
Quote:
Originally Posted by kriesel View Post
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 View Post
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 View Post
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
kriesel is online now   Reply With Quote
Old 2021-09-27, 16:18   #20
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

100110001110112 Posts
Default

Moved to misc math, renamed properly.
LaurV is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 20:20.


Sun Oct 24 20:20:39 UTC 2021 up 93 days, 14:49, 2 users, load averages: 1.02, 1.43, 1.42

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.