mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2020-03-18, 13:19   #34
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by LaurV View Post
Threads merged and moved to programming.

There was no reason to split threads, the initial thread already gave all the answers, including from RDS, who was actually quite right. The fact you don't like the answers is not a reason to clutter.
Yes there was. This wasn't a question about programming but rather about certain edge cases. The programming part was merely providing context as to why I was interested in it.

Quote:
Originally Posted by LaurV View Post
You are using java (terrible slow, interpreted, not compiled, no FFT multiplication, which translates to thousands of times slower than a "normal" gmp or gwnum implementation, and it is limited for integer size to 40k bytes or so, therefore completely futile to test any reasonable exponent)
I fail to see the relevance. My goal is not to create a fast implementation. My goal is to create the fastest implementation under some restrictions. Which in this case are using the BigInteger library in Java.
I never claimed that it would make sense to do so. I am doing it because I enjoy playing with numbers. And also because I want to practise optimizing things in Java. Because that's part of my job.

And all those things are irrelevant to the underlying math question.

Quote:
Originally Posted by LaurV View Post
, but in the same time you seem to be quite nitpicking on subtracting 2 before or after taking the modular from the square. People gave you already a better way to avoid division taking advantage of the binary form of the modulus, which would double the speed (not in pari, bitand is terrible slow there), with or without subtracting 2, and you are still fixed on that subtracting 2. C'mon man, it is like racing a tractor against a ferrary and trying to make your tractor faster by changing the position of the mirror or something, to avoid "catching the wind", or throwing out the knob of the handbrake because "it is too heavy".

Listen to these guys, they know what they are talking.
In summary I wasn't aware of the fast mod. So I tried optimizing the small things as those were the obvious things to try. And my obsession with -2 comes from the fact that I'd like to make sure that the implementations are 100% correct. Hence I'd like to make sure they pass edge cases. And \(S(n) = 1\) would be such an edge case.

But in turn let me ask you this:
What is your (all) obsession with essentially telling me I'm not allowed to (or shouldn't) do things I enjoy for the sake of doing them? I mean think about it. The entire premisse of this forum is based on a futile matter. Finding Mersenne Primes has no merrit to it other than creating utterly obscure knowledge that most likely will never be relevant. And why do people do that? Because they enjoy doing it or because they are curious. The exact same applies to what I am doing.
Now you might say things like "But math is math. Every bit of knowledge is valuable. And one day it might be important". And to that I say "Rightfully so. And knowing which way to implement LL using Java's BigInteger is the fastest is exactly the same." Or "While doing so many important things have been discovered along the way". And my response would be that the same applies to my case. Even if only I learn doing it.

And regarding R.D. Silverman's answer:
I asked a yes-no question (does such a case exist). And the reply was a mathematical explanation that I don't understand. So while this may be answer to you, it isn't to me. I can't tell if their answer means "Yes, such cases are possible" or "No. No such cases are possible". Though if I had to guess, it's a yes and that we haven't found any such cases so far.

But I get it. Uneducated people are not welcome here and neither are people that enjoy doing "futile" things for the sake of it.
BrainStone is offline   Reply With Quote
Old 2020-03-18, 13:37   #35
axn
 
axn's Avatar
 
Jun 2003

33·173 Posts
Default

Quote:
Originally Posted by BrainStone View Post
But I get it. Uneducated people are not welcome here and neither are people that enjoy doing "futile" things for the sake of it.
So you got criticized. Doesn't mean you or your ideas are unwelcome. But doesn't mean your ideas get a free pass either. You are free to choose which criticisms you take to heart and which you ignore.

Anyway, do you want to know what's funny about your concerns with encountering negative numbers? It doesn't matter! Java biginteger uses signed integers, and so even if you run into negative numbers, the squaring operation in the next iteration will still give you correct value! Try it.

One thing that bugs me though. You said that S.multiply(S).mod(M_p).subtract(2).mod(M_p) benchmarked a little bit faster than S.multiply(S).mod(M_p).subtract(2). Since the former does strictly more operations than the latter, I have to assume that perhaps your benchmarking is somehow flawed. Maybe they're close enough that you're measuring statistical variation, but I can't believe that the first one can ever be faster than the second.
axn is offline   Reply With Quote
Old 2020-03-18, 13:41   #36
kuratkull
 
kuratkull's Avatar
 
Mar 2007
Estonia

2·67 Posts
Default

Doing some back-of-the-napkin math here, which might not be correct - I am not a mathematician, but a software engineer.
We have N=2^n-1. Let's assume n "tries" to get 1 as a result of the mod operation.
The result can be 0..N.. So every single try has 1/N chance of being 1. (I am leaving out the fact that the result first has to reach N)
So the chance of a candidate becoming 1 is roughly: 1/(2^n)*n
This chance becomes miniscule very quickly, eg. n=64 is circa 10^-18. n=128 is circa 10^-37
So it's practically impossible to hit that condition. Am I right?

Last fiddled with by kuratkull on 2020-03-18 at 13:50
kuratkull is offline   Reply With Quote
Old 2020-03-18, 14:12   #37
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by axn View Post
So you got criticized. Doesn't mean you or your ideas are unwelcome. But doesn't mean your ideas get a free pass either. You are free to choose which criticisms you take to heart and which you ignore.
We're well past critizism. We're at the point that I quite frankly feel ridiculed. And most of the thread has been critizism of futile points and things not related to the question.
There's a saying that if you don't have anything nice or constructive to say, don't say anything. And critizing me for using an inefficient (in the grand scheme of things) method of doing things when absolute efficiency isn't a concern of mine is not constructive. And said point has been repeated numerous times already.

Quote:
Originally Posted by axn View Post
Anyway, do you want to know what's funny about your concerns with encountering negative numbers? It doesn't matter! Java biginteger uses signed integers, and so even if you run into negative numbers, the squaring operation in the next iteration will still give you correct value! Try it.
At this point I agree. I know that it is a signed type. My initial concerns were that hitting a negative value might result in false negatives. Though since hitting a negative value will always result in a loop there can't be any false negatives.
And while I initially doubted that it could matter at all, I wasn't sure initially, so I wanted to have test cases that covered it.

So I am aware that this discussion only has a pure mathematical value left, which is makes me disagree even more with the decision to merge the threads and move it into Programming, where it now is severely misplaced.

Quote:
Originally Posted by axn View Post
One thing that bugs me though. You said that S.multiply(S).mod(M_p).subtract(2).mod(M_p) benchmarked a little bit faster than S.multiply(S).mod(M_p).subtract(2). Since the former does strictly more operations than the latter, I have to assume that perhaps your benchmarking is somehow flawed. Maybe they're close enough that you're measuring statistical variation, but I can't believe that the first one can ever be faster than the second.
It's very well possible that that's the case. Though since it is Java and Java handles memory in a strange way it could be that through memory schenanigans it does weird stuff.
BrainStone is offline   Reply With Quote
Old 2020-03-18, 14:13   #38
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by kuratkull View Post
Doing some back-of-the-napkin math here, which might not be correct - I am not a mathematician, but a software engineer.
We have N=2^n-1. Let's assume n "tries" to get 1 as a result of the mod operation. (I am leaving out the fact that the result first has to reach N)
The result can be 0..N.. So every single try has 1/N chance of being 1.
You are not listening. And despite your claim, it is clear that you do not understand
modular arithmetic. In particular you did not listen to my discussion about
representations.

Arithmetic mod N can never yield a result that is in [0,.....N] because N is not part of
the representation. It can be [0,....N-1]. Because, trivially N mod N equals 0.
When working mod N the expression [0,....N] is not a set. It is a multi-set.

Secondly, your assertion that "The result can be 0..N.. So every single try has 1/N
chance of being 1." is also wrong. There are N+1 elements in 0,....N , not
N. Your statement also assumes a uniform pdf which assuredly it is NOT.

You are a software engineer trying to implement an algorithm whose correct
implementation requires knowing a lot of math. Multiple people have told you that
the "-2" is irrelevant to the run-time. Yet you continue to argue with them.

Quote:

So the chance of a candidate becoming 1 is roughly: 1/(2^n)*n
I will assume that by the word "becoming" you mean "becoming before reaching the last
iteration".

Your assertion is totally wrong. If N = 2^p-1 is prime the probability is zero. If N is
composite the probability depends on the factors of N+1 and the structure of the
subgroups of the twisted group, i.e. it depends on the number of elements whose order
is r for r less than the full order. The values of r depend on the factors of N+1.



Quote:
This chance becomes miniscule very quickly, eg. n=64 is circa 10^-18. n=128 is circa 10^-37
So it's practically impossible to hit that condition. Am I right?
You are not. It is totally impossible to hit it if N is prime. If N is composite see above.

You state that you are not a mathematician, yet you make mathematical pronouncements
when you don't know the math. I call that arrogant.

Stop making pronouncements and start listening. You will need to learn some
modern algebra, some number theory, and some statistical theory.

Last fiddled with by R.D. Silverman on 2020-03-18 at 14:16 Reason: pagination
R.D. Silverman is offline   Reply With Quote
Old 2020-03-18, 14:16   #39
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by kuratkull View Post
Doing some back-of-the-napkin math here, which might not be correct - I am not a mathematician, but a software engineer.
We have N=2^n-1. Let's assume n "tries" to get 1 as a result of the mod operation.
The result can be 0..N.. So every single try has 1/N chance of being 1. (I am leaving out the fact that the result first has to reach N)
So the chance of a candidate becoming 1 is roughly: 1/(2^n)*n
This chance becomes miniscule very quickly, eg. n=64 is circa 10^-18. n=128 is circa 10^-37
So it's practically impossible to hit that condition. Am I right?
I fully agree with your reasoning (Turns out that was wrong. That's why I like to ask knowledgable people ;) ). But practically impossible doesn't mean impossible. I mean Mersenne Primes become increasingly less likely but there most likely are more and it's certainly beneficial to consider rare edge cases.

Though as pointed out, programmically speaking it's a non concern. So now I'm just genuinely curious as to whether or not those cases might exist.

Last fiddled with by BrainStone on 2020-03-18 at 14:18
BrainStone is offline   Reply With Quote
Old 2020-03-18, 14:21   #40
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
If N is
composite the probability depends on the factors of N+1 and the structure of the
subgroups of the twisted group, i.e. it depends on the number of elements whose order
is r for r less than the full order. The values of r depend on the factors of N+1.
Do I understand correctly that there are cases that consequently allow it to become 1?
BrainStone is offline   Reply With Quote
Old 2020-03-18, 14:21   #41
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

27D816 Posts
Default

Quote:
Originally Posted by BrainStone View Post
We're well past critizism. We're at the point that I quite frankly feel ridiculed.
Chill. Everyone here who posts more than few times gets ridiculed eventually. And I mean everyone.

Learn from it by not repeating your error / naivety / whatever and any cases which can be easily deduced from the reaction to it.
xilman is online now   Reply With Quote
Old 2020-03-18, 14:27   #42
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by BrainStone View Post
We're well past critizism. We're at the point that I quite frankly feel ridiculed. And most of the thread has been critizism of futile points and things not related to the question.
There's a saying that if you don't have anything nice or constructive to say, don't say anything. And critizing me for using an inefficient (in the grand scheme of things) method of doing things when absolute efficiency isn't a concern of mine is not constructive. And said point has been repeated numerous times already.
I gave a complete (expressed in elementary terms) mathematical explanation.
A mature person who did not understand it, yet still desiring to do this work would take
the time to go learn the math. Yes, it takes a lot of time. One can't correctly
implement a mathematical algorithm without understanding the math.

The first question you should have asked was "What do I need to learn in order to
correctly implement this algorithm".




Quote:

At this point I agree. I know that it is a signed type. My initial concerns were that hitting a negative value might result in false negatives.
Yet, you did not ask that question. And you personally were not being criticized. Your
statements were. If you can't stand to have your discussion criticized then you
need to find another venue.
R.D. Silverman is offline   Reply With Quote
Old 2020-03-18, 14:29   #43
kuratkull
 
kuratkull's Avatar
 
Mar 2007
Estonia

2·67 Posts
Default

R.D. Silverman - I think you mixed me up with the OP. I am not trying to implement anything, I already did: https://github.com/dkull/rpt
Most of the stuff you commented on was left out/ignored for brevity. It bears no significant weight on the magnitude of the final calculation.
I think starting with a disclaimer and ending with a question about correctness leaves little room for arrogance.
kuratkull is offline   Reply With Quote
Old 2020-03-18, 14:31   #44
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

111112 Posts
Default

Quote:
Originally Posted by xilman View Post
Chill. Everyone here who posts more than few times gets ridiculed eventually. And I mean everyone.

Learn from it by not repeating your error / naivety / whatever and any cases which can be easily deduced from the reaction to it.
What error did I do? I was upfront about that I know that what I'm doing isn't productive after my choice of programming language and library was (correctly) critizised the first time. I've then provided my motivation and justification to use it, which prompted unwarrented ridicule.

It's like saying I want to race with a tractor (to pick up on a previous analogy). Then being critizised that that is a bad choice (which is correct). I proceeded to explain that I enjoy racing with tractors and that I don't want to anything but race tractors. Which then resulted people continuing to critize my choice of vehicle, even though it was clear that I was fully aware of the downsides and was chosing for very different reasons.
That's just being rude and inappropriate.
BrainStone is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
A second proof for the Lucas-Lehmer Test carpetpool Miscellaneous Math 2 2017-07-30 09:21
Lucas-Lehmer test Mathsgirl Information & Answers 23 2014-12-10 16:25
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas Lehmer test question? BMgf Programming 23 2003-12-09 08:52

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

Thu Aug 13 20:26:32 UTC 2020 up 17:02, 1 user, load averages: 1.60, 1.95, 2.00

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.