mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Programming (https://www.mersenneforum.org/forumdisplay.php?f=29)
-   -   Can the subtraction in the lucal lehmer test ever return a negative value? (https://www.mersenneforum.org/showthread.php?t=25373)

 kuratkull 2020-03-17 13:23

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.

 axn 2020-03-17 13:24

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.

 retina 2020-03-17 13:24

[QUOTE=BrainStone;539934]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.[/QUOTE]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.

 BrainStone 2020-03-17 13:33

[QUOTE=kuratkull;539935]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.[/QUOTE]

Of course. As I said I've seen libraries that implement their [C]mod[/C] to behave like the [C]%[/C] operator would.

[QUOTE=axn;539936]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.[/QUOTE]

No, I haven't. I'll certainly give this a try.

[QUOTE=retina;539937]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.[/QUOTE]

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 2020-03-17 13:45

[QUOTE=axn;539936]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.[/QUOTE]

That calculation does not seem to work.

 axn 2020-03-17 15:20

[QUOTE=BrainStone;539940]That calculation does not seem to work.[/QUOTE]

Can you post your code snippet?
EDIT:- For some values, you might have to do a second reduction.

 R.D. Silverman 2020-03-17 15:43

[QUOTE=BrainStone;539930]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.

[/QUOTE]

If your concern is actual computer implementation of a library then I must ask:

Why post in the [b][i] math [/i][/b] subforum?? Your question is not math-related.

There is a programming subforum. Use it instead.

 BrainStone 2020-03-17 15:44

[QUOTE=axn;539946]Can you post your code snippet?
EDIT:- For some values, you might have to do a second reduction.[/QUOTE]

[CODE]
public static final BigInteger fastMod(BigInteger number, BigInteger candidate, int prime) {
}
[/CODE]

[C]number[/C] is the [$]S[/$] in the LL test, [C]candidate[/C] is [$]M_p[/$] and [C]prime[/C] is [$]p[/$].

 BrainStone 2020-03-17 15:47

[QUOTE=R.D. Silverman;539947]If your concern is actual computer implementation of a library then I must ask:

Why post in the [B][I] math [/I][/B] subforum?? Your question is not math-related.

There is a programming subforum. Use it instead.[/QUOTE]

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.

 R.D. Silverman 2020-03-17 15:51

[QUOTE=retina;539920]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 [i]might[/i] work.

[size=1]Premature optimisation?[/size][/QUOTE]

This is supposed to be the [b]math[/b] subforum.

:direction:

 paulunderwood 2020-03-17 15:58

[QUOTE=axn;539936]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.[/QUOTE]

[C]bitand[/C] and [C]&[/C] behave differently in Pari/GP. Is there a bit wise and for Java?

All times are UTC. The time now is 17:08.