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

[Michael Leitner]

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

I would not say that it is always a bad idea to put a switch into a for-loop.
Sometimes, it is even the best idea, for instance here when one wants to
execute the same code with different primes lists, without calling a function.
I agree that your solution with a function is definitely more elegant, and in
a compiled language the compiler would care about making it efficient (such as
by inlining). Octave is not compiled, and function calls really cost more than
just the execution of the code they contain, that's why I consciously avoided
this solution in patch2. However, I did not test, and it is only two function
calls which probably do not make much difference, in any case not when you
factor numbers beyond flintmax. 

But this is my other point: I think that you put much too strong weight onto
the behaviour at such large inputs. I think that most users, when they have to
factorize a given very large number once (like you tell in comment #6) would
just go to Wolfram Alpha. I was not even aware that factor.m works at all with
uint64 input beyond flintmax (I think there are quite a number of functions in
octave that fail either silently or noticeably in this case). Yes, factorizing
a single small number once returns immediately, both with the original version
or with any of the patches. However, for me the main issue is when factor.m is
called repeatedly in a loop with different inputs (of reasonable magnitude) --
 but of course in this situation it would be clearly better to compute a large
list of primes once and use it always. 

And as we are talking about good and bad styles of programming, the only
comment I still have with respect to your patch4 is about the note starting in
line 69: indeed, I would call the commented-out command in line 70 an example
of an octave-antipattern -- it has to make a copy of largeprimes, resize it,
and overwrite largeprimes. The command in line 72 is slightly better, as it
generates the new largeprimes directly from the index vector. However, both
are very inefficient, as the comparison has to be done for every prime, and
the copying is unnecessary. The most obvious solution would be to do

++
largeprimes = primes (sqrt (q))(1+length (smallprimes):end);
--

in line 68 -- in this case, there is no copying, as the result of primes()
never enters the scope, but stays in memory, while the resulting largeprimes
is a reference to this object, starting at some later element. In all
probability, it won't make much difference, as these first elements are
immediately thrown out in  reducefactors(), but at least I would think that it
doesn't slow down the execution. And the corresponding line 

++
divisors (mod (q, divisors) ~= 0) = []; # throw out non-factors
--

is the next octave-antipattern, I suggest to change that to

++
divisors = divisors (mod (q, divisors) == 0); # keep only factors
--



    _______________________________________________________

Reply to this item at:

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

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