mersenneforum.org Can the subtraction in the lucal lehmer test ever return a negative value?
 Register FAQ Search Today's Posts Mark Forums Read

 2020-03-17, 13:23 #12 kuratkull     Mar 2007 Estonia 2×67 Posts 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
 2020-03-17, 13:24 #13 axn     Jun 2003 11×421 Posts 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.
2020-03-17, 13:24   #14
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

23·691 Posts

Quote:
 Originally Posted by BrainStone 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.

2020-03-17, 13:33   #15
BrainStone

Nov 2017
Karlsruhe, Germany

31 Posts

Quote:
 Originally Posted by kuratkull 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 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 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.

2020-03-17, 13:45   #16
BrainStone

Nov 2017
Karlsruhe, Germany

31 Posts

Quote:
 Originally Posted by axn 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

2020-03-17, 15:20   #17
axn

Jun 2003

11·421 Posts

Quote:
 Originally Posted by BrainStone 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

2020-03-17, 15:43   #18
R.D. Silverman

Nov 2003

2×3×17×73 Posts

Quote:
 Originally Posted by BrainStone 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.

2020-03-17, 15:44   #19
BrainStone

Nov 2017
Karlsruhe, Germany

31 Posts

Quote:
 Originally Posted by axn 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) {
}
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

2020-03-17, 15:47   #20
BrainStone

Nov 2017
Karlsruhe, Germany

31 Posts

Quote:
 Originally Posted by R.D. Silverman 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

2020-03-17, 15:51   #21
R.D. Silverman

Nov 2003

2×3×17×73 Posts

Quote:
 Originally Posted by retina 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.

2020-03-17, 15:58   #22
paulunderwood

Sep 2002
Database er0rr

13·251 Posts

Quote:
 Originally Posted by axn 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 carpetpool Miscellaneous Math 2 2017-07-30 09:21 Mathsgirl Information & Answers 23 2014-12-10 16:25 storm5510 Math 22 2009-09-24 22:32 BMgf Programming 23 2003-12-09 08:52

All times are UTC. The time now is 02:31.

Sat Jul 4 02:31:54 UTC 2020 up 101 days, 4 mins, 1 user, load averages: 2.12, 1.51, 1.27