mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2020-03-17, 13:23   #12
kuratkull
 
kuratkull's Avatar
 
Mar 2007
Estonia

2048 Posts
Default

Prime95, LLR64, and even my own implementation use the gwnum library for the core multiplication/subtraction/modulus, not the builtin %, which works only on native ints. Before I wrote my final implementation I created a demo in Python, with GMP doing the heavy lifting. This solution was several times slower than the final compiled+gwnum solution. This is due to relatively slow loops in Python (an issue Java shouldn't have due to probably effective jit-ing of loops), but GMP itself was too slow for this exact problem. gwnum handles the -2 almost for free, and it's geared towards being very good with multiplication/products mod N. Also it transfers some info from one multiplication to the next (with some special calls) which also speeds it up. Naive solutions are going to be dead slow. gwnum also parallelizes the calculation, uses intrinsics and uses handwritten assembly for the FFT.

Last fiddled with by kuratkull on 2020-03-17 at 13:37
kuratkull is offline   Reply With Quote
Old 2020-03-17, 13:24   #13
axn
 
axn's Avatar
 
Jun 2003

11F016 Posts
Default

Have you tried implementing S mod Mp as (S & Mp) + (S >> p) ? This ought to be much faster than generic Java biginteger mod. Then you can add additional safety checks to your heart's content.
axn is offline   Reply With Quote
Old 2020-03-17, 13:24   #14
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

10101001110102 Posts
Default

Quote:
Originally Posted by BrainStone View Post
I never claimed it was a good choice.
My concerns about negative numbers are independent of that hower because calculating the modulus like I described is fairly common in computer science. And I've seen my fair share of big int libraries that calculate their mod like that.


And yes there is a need. Because between the best and worst method I've tested so far, the fastest is roughly twice as fast as the slowest.
But all your tests are with Java. So they mean nothing when you start to use a proper and useful implementation. You are wasting your time.
retina is online now   Reply With Quote
Old 2020-03-17, 13:33   #15
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

1F16 Posts
Default

Quote:
Originally Posted by kuratkull View Post
Prime95, LLR64, and even my own implementation use the gwnum library for the core multiplication/subtraction/modulus, not the builtin %, which works only on native ints.
Of course. As I said I've seen libraries that implement their mod to behave like the % operator would.

Quote:
Originally Posted by axn View Post
Have you tried implementing S mod Mp as (S & Mp) + (S >> p) ? This ought to be much faster than generic Java biginteger mod. Then you can add additional safety checks to your heart's content.
No, I haven't. I'll certainly give this a try.

Quote:
Originally Posted by retina View Post
But all your tests are with Java. So they mean nothing when you start to use a proper and useful implementation. You are wasting your time.
Whether I waste my time or not is still on my part, isn't it? I do it because I want to familiarize myself with microbenchmarking in Java and because I enjoy playing around with numbers like that. I never claimed to be productive however.
Though keep in mind that there will always be legitemate reasons to calculate LL in pure Java.
BrainStone is offline   Reply With Quote
Old 2020-03-17, 13:45   #16
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by axn View Post
Have you tried implementing S mod Mp as (S & Mp) + (S >> p) ? This ought to be much faster than generic Java biginteger mod. Then you can add additional safety checks to your heart's content.
That calculation does not seem to work.

Last fiddled with by BrainStone on 2020-03-17 at 13:53
BrainStone is offline   Reply With Quote
Old 2020-03-17, 15:20   #17
axn
 
axn's Avatar
 
Jun 2003

459210 Posts
Default

Quote:
Originally Posted by BrainStone View Post
That calculation does not seem to work.
Can you post your code snippet?
EDIT:- For some values, you might have to do a second reduction.

Last fiddled with by axn on 2020-03-17 at 15:29
axn is offline   Reply With Quote
Old 2020-03-17, 15:43   #18
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

23·32·103 Posts
Default

Quote:
Originally Posted by BrainStone View Post
R.D. Silverman, I have a fair understanding of modulus and equivalence classes.
And I do know that the iteration is \(S \left( n + 1 \right) \equiv \left( {S \left( n \right)}^2 - 2 \right) mod M_p\). The math here is pretty clear.

However in terms of optimization we are in the realms of programming and computer science. And while they are inherently linked there are some differences.
If your concern is actual computer implementation of a library then I must ask:

Why post in the math subforum?? Your question is not math-related.

There is a programming subforum. Use it instead.
R.D. Silverman is offline   Reply With Quote
Old 2020-03-17, 15:44   #19
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by axn View Post
Can you post your code snippet?
EDIT:- For some values, you might have to do a second reduction.
Code:
    public static final BigInteger fastMod(BigInteger number, BigInteger candidate, int prime) {
        return number.and(candidate).add(number.shiftRight(prime));
    }
number is the \(S\) in the LL test, candidate is \(M_p\) and prime is \(p\).

Last fiddled with by BrainStone on 2020-03-17 at 15:46
BrainStone is offline   Reply With Quote
Old 2020-03-17, 15:47   #20
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
If your concern is actual computer implementation of a library then I must ask:

Why post in the math subforum?? Your question is not math-related.

There is a programming subforum. Use it instead.
Because my question is if there's ever a case where \(S(n) \equiv 1 \mod M_p\). Why I am asking this is merely giving context.

Last fiddled with by BrainStone on 2020-03-17 at 15:48
BrainStone is offline   Reply With Quote
Old 2020-03-17, 15:51   #21
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

23×32×103 Posts
Default

Quote:
Originally Posted by retina View Post
BrainStone: It doesn't matter. When you do the subtraction, if you get an overflow then adjust it to within range, if you don't, then do nothing. I don't see the big deal, it might never overflow and then it costs you nothing. Then it will work for ALL values; rather than praying, hoping and guessing that it might work.

Premature optimisation?
This is supposed to be the math subforum.

R.D. Silverman is offline   Reply With Quote
Old 2020-03-17, 15:58   #22
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,209 Posts
Default

Quote:
Originally Posted by axn View Post
Have you tried implementing S mod Mp as (S & Mp) + (S >> p) ? This ought to be much faster than generic Java biginteger mod. Then you can add additional safety checks to your heart's content.
bitand and & behave differently in Pari/GP. Is there a bit wise and for Java?

Last fiddled with by paulunderwood on 2020-03-17 at 15:58
paulunderwood is online now   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 03:20.

Sun May 31 03:20:23 UTC 2020 up 67 days, 53 mins, 1 user, load averages: 1.32, 1.55, 1.41

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.