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

[Michael Leitner]

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

I just tested a bit, and it seems that the Schrage recursion often (always?)
ends up with b equal to 0, but r>=q, thus going further in the recursion,
where obviously it could already return. So I seem to get about a factor of
two improvement if in the body of savemultiply I define

++
  if (a < 2) return a * b;
  uint64_t q = modulus / a;
  uint64_t r = modulus - q*a;
  uint64_t term1 = a * (b % q);
  uint64_t d = b / q;
  uint64_t term2 = (r < q) ? r * d : r < d ? safemultiply (r, d, modulus) :
safemultiply (d, r, modulus);
  return (term1 > term2) ? (term1 - term2) : (term1 + modulus - term2);
--

You see that additionally I indeed call safemultiply (at least in the
recursion) so that the first factor is the smaller as I proposed below -- this
seems to give also about 10%, but perhaps it would be worth to test this
further.

    _______________________________________________________

Reply to this item at:

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

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