[Octave-bug-tracker] [bug #61129] Performance of factor(). Proposed patch attached.

[Michael Leitner]

Follow-up Comment #7, bug #61129 (project octave):

Yes, as I wrote below, by using in the first round a primes list with a length
that depends on the input, you can cut down on the average execution time.
This makes the code more complex, but yes, a simple if won't take so much
time. 

However, I still would say that from a general point of view of code
readability, it is much better to see this as two rounds of the same
algorithm, the first time with a small list of primes to reduce q, and the
second time with the full list of all possible primes. Thus, the approach as
in patch2 is to be preferred from my point of view, while in your patches the
two rounds are distinct pieces of code and even use different operations (mod
as opposed to rem, and testing only single primes as opposed to the full
list). And note that in your patch3 you test the first primes in both rounds.


You can modify patch2 to make it as efficient as patch3 (or even slightly more
efficient, as all primes are tested only once) by inserting your distinction
whether q>=20e9 into the i==1 case, exporting the length of the resulting
smallprimes list in Nsmall, and using the part (Nsmall:end) of the full primes
list in the else branch. Casting the smallprimes list to the class of the
input is a good catch, and of course you can gain additional efficiency for
small inputs by taking a longer hard-coded list of primes. Hundred is not
excessive, I would say, and indeed also in primes.m itself these first hundred
primes are hard-coded for increased efficiency. 

    _______________________________________________________

Reply to this item at:

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

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