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

[Michael Leitner]

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

With respect to performance: I disagree. First, I would not quote three
significant digits as a general performance increase when you test it by a
very specific sample. 

Yes, at large (to be specific: extremely large) inputs your solution will be
faster, because your approach uses a larger list of primes in the first round,
which will sometimes reduce q so that in the second round you need to do the
prime sieve only for a significantly smaller size, while my approach always
only uses ten primes. Of course you are free to enlarge the hard-coded list,
and you could even do your approach of using a list with a length that depends
on the input. However, this needs more operations (in your solution, a
rational power), and it is questionable whether in the typical case of use
this is beneficial or not. Indeed, one of the two distinguishing points of my
patch is to use a hard-coded list as opposed to compute the prime sieve. And I
would say that in the typical case of use this is beneficial: 

++
tic;for i=1:10000 factor(i);end;toc
--

takes 3.9 seconds for the existing factor, 5.5 seconds with your patch, and
3.3 with mine (and if we increase the hard-coded list to 100 entries, it is
down at 2.8 seconds).

Now to accuracy: In fact, the second distinguishing point of my patch was to
use the same code for the two runs (first with the small list of primes, then
for the full list computed with the prime sieve according to the reduced q) --
it iteratively takes the list of primes that fulfill rem (q, p) == 0 and
divides by their product. In your case, in the first run you step through the
reduced list one by one, and then divide only by the prime to the power of one
if it fulfills mod(q,pp) == 0 (which for positive q and pp should be
equivalent to mod, I think). 

Now the input 15999999832000000434 (for those who want to try that: you really
have to compute it as the square of the uint64, as this is beyond flintmax,
and I know of no way to give uint64 literals in octave) you mention factorizes
as 2*3*2666666638666666739. Indeed, the order of divisions in the three
versions is different, but as I understand, if you have an operation with a
least one operand being an uint, the result will be an uint, and if it is
exactly representable (which should be the case for divisions by divisors), it
should be the arithmetically correct result. Thus, I do not understand how the
three versions can differ. I cannot do the calculation as my memory is too
small to compute the prime sieve. Can you tell me the respective results?

    _______________________________________________________

Reply to this item at:

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

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