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

[Arun Giridhar]

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

Patch 5 attached with two more improvements:

1. This version of isprime uses Schrage multiplication and eliminates the
safeadd utility function. The average execution time is decreased from 30
microseconds to 18 microsecongs, and the code is shorter. An entry has been
made in NEWS if it is appropriate.

2. The related function factor(), which was recently sped up for composite
numbers but was still slow for large prime numbers, now uses the patched
version of isprime() to return immediately if its input is prime, meaning that
factor() now becomes several orders of magnitude faster for ALL inputs, not
just composite ones. The corresponding NEWS item has been edited.

Patch 5 attached. Please test and benchmark using the benchmark code in
comment #2.

(file #52112)
    _______________________________________________________

Additional Item Attachment:

File name: patch5.patch                   Size:9 KB
    <https://file.savannah.gnu.org/file/patch5.patch?file_id=52112>



    _______________________________________________________

Reply to this item at:

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

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