Can the subtraction in the lucal lehmer test ever return a negative value?

[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. 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]

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]

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.

[BrainStone]

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.

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.

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.

[BrainStone]

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.

[axn]

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.

[R.D. Silverman]

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.

[BrainStone]

Originally Posted by axn

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

    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\).

[BrainStone]

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.

[R.D. Silverman]

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.

[paulunderwood]

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?