[Octave-bug-tracker] [bug #61312] Extending isprime() with Miller-Rabin test

[Arun Giridhar]

Follow-up Comment #15, bug #61312 (project octave):

I found a bigger problem with the patch. Let me work on that first before
changing the Schrage part.

Try this stress test for 10 million numbers:

n = 4294967295 - (0:9999999); tic; isprime(n); toc


With unpatched Octave (straight division), it takes 26.4 seconds.
With the patched Octave (Miller-Rabin), it takes 69.9 seconds.

Clearly there needs to be some tuning of the threshold so that numbers smaller
than say 2^32 or 10^10 are tested by straight division. But raising the prime
threshold above 37 causes the Miller-Rabin performance for large numbers to
suffer, so it may be prudent to split the inputs into two parts, those below
say 2^32 and those above, like in Patch 1 all the way at the bottom. I don't
know the better answer yet.

For inputs that include both numbers less than 2^32 and numbers larger than
say 2^53, the Miller Rabin test is very much faster. For numbers near 10^19,
it's much faster. But the threshold cannot be as low as 37 evidently.

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?61312>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/