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

[Arun Giridhar]

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

Thanks, Markus. I have added the tag inside the error BIST. The spacing near
function names and negation operators has been checked. I edited the comments
to match the style, and I reversed a for-loop in the C++ code to avoid
repeated calls to numel() in case it was not cached. "Make check" passes.

Patch attached.

Re the speedup, if I run this for the very top end of the 64-bit range:

n = intmax("uint64") - 58;   # n = 2^64 - 59, the largest 64-bit prime
tic; isprime(n); toc


Results:
Old code:  Elapsed time is 20.1576 seconds.
New code:  Elapsed time is 0.000178099 seconds.
Ratio = 20.1576 / 0.000178099 = 113,182.

Saying it is 50,000 times faster for some large inputs actually might be
conservative, but that's OK since it's more representative of a wider range,
from 1x at the threshold (29 billion) to over 100,000x at 2^64. For inputs
below the threshold, it retains the use of the conventional division technique
because that is faster for smaller inputs.

(file #52173)
    _______________________________________________________

Additional Item Attachment:

File name: patch_clean.patch              Size:14 KB
    <https://file.savannah.gnu.org/file/patch_clean.patch?file_id=52173>



    _______________________________________________________

Reply to this item at:

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

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