On Inefficiencys about open.numeric.primes HOT 9 OPEN

Hello! Just checking in. I'll read in detail tomorrow and respond more.
Always appreciate feedback. Anywhere I can make improvement... it will be done!

Note: when it comes to primality checks, the "Optimized" version (the default) makes choices to select which algorithm will perform better for the size of the number. Smaller numbers will typically use Polynomial, and with larger numbers, Miller-Rabin will be used with some ulong to verify primality, and BigInteger will use Miller-Rabin to exclude non-primes and then verify primality with Polynomial.

https://github.com/Open-NET-Libraries/Open.Numeric.Primes/blob/master/source/Optimized.cs
The default use typically gets routed to this instance:
https://github.com/Open-NET-Libraries/Open.Numeric.Primes/blob/master/source/Primes.cs#L125

from open.numeric.primes.

In the File "Open.Numeric.Primes/source/MillerRabin.cs"

Providing the option to use it, is fine.
Someone either has to explicitly use it, or it has to be a big enough number for the default to attempt it.

from open.numeric.primes.

Line 45 "
ref readonly var b = ref ar[i]; // i dont know why you would use "ref readonly var" instead of "ulong"

I'm attempting to use this feature of C# ReadOnlySpan<ulong> to avoid creating copies of the number contained.
This may be a moot attempt at performance as it may or may not help given the choice between copying a 64 bit number and setting a 64 bit pointer. I was concerned that in a 32-bit application it may provide a benefit. Hence why you will see the optional in modifier in places where parameters are 64 bit or greater.

from open.numeric.primes.

var a = value - 2; // I dont know what that is, that's not part of the algorithm
var now = a > b // again, no clue, that's not part of the algorithm
? Pow(in b, in d, in value) // again, no clue, that's not part of the algorithm
: Pow(in a, in d, in value); // again, no clue, But nice try avoiding branch miss using Conditional moves xDD

This is done instead of Math.Min. The result is the same, but can then leverage the in version of the Pow method.

from open.numeric.primes.

in is a newer keyword in C# that provides a couple benefits:

1. The number cannot be modified by the function called and so even though it's a reference, the caller can assume the number did not change. (There might be some compiler optimizations around this, but I can't say.)
2. For larger structs and value types, instead of making a 'copy' of the value for the function to consume, it's the reference instead. This has a dramatic effect on BigInteger use and other structs. Maybe not so much for 64 bit values, potentially detrimental for 32 bit (and doubles), and useless for reference types.

from open.numeric.primes.

okey looks complicated, it looks like a really cryptic recursive D&C Power algorithm.
So that really slow. each recursion will get written on the Stack + Call Overhead + Pipeline flushes + unnecessary Overhead.
Write on without recursion ( i assume it would be at least 10 times faster ).

Since I'm really adapting what someone else wrote, I'm not sure how this could be improved.
I'm trying to make sure the code is clean and easy to read with some nice statics that avoid recursion where possible.
As well as a separation of ulong and BigInteger.
Can you advise what I should change here?

from open.numeric.primes.

So I'm aware of the wrap-around possibility and try to avoid issues with that where possible.
You'll see in other places, I check to see what numbers will cause the wrap-around and then up-level it to a higher number type if needed. But I may have missed it here.

from open.numeric.primes.

It would be great if you cloned the repo, made a branch with the suggested changes and I can test.
If you wanna focus on one aspect at a time for each change, then I can incrementally test them.
If there's something more GCE (gross conceptual error) that I may have done, maybe a different implementation entirely is required?

from open.numeric.primes.

Here are the current speed test results I have: (thanks for the trial division help/fix)

Singular Trial Division Tests:
00:00:00.0000744 U32 Benchmark
00:00:00.0000773 U32
00:00:09.7749346 U64 Benchmark
00:00:08.6137033 U64

Batch Tests:
00:00:00.0013936 Polynomial.U32
00:00:00.0014005 Optimized
00:00:00.0122794 Polynomial.U64
00:00:00.0428230 MillerRabin.U64
00:00:00.1061931 TrialDivision.U64.Memoized Cached
00:00:01.4419965 TrialDivision.U32.Memoized
00:00:02.1333997 TrialDivision.U64.Memoized
00:00:02.5321315 TrialDivision.U32
00:00:05.4558333 TrialDivision.U64

If you are correct, then at least one of these numbers should improve.
I could definitely add more tests and do more focus on Miller-Rabin.

from open.numeric.primes.