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

[anonymous]

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

Thanks for the improvements in comment #10. I profiled the variants "foo(~ii)
= []" and "foo = foo(ii)" over a few million trials, and the second takes 3.7
milliseconds while the first takes 4.3 milliseconds. Adopted the second
variant. The suggestion to use length(smallprimes) instead of max(smallprimes)
is good -- I've made that change.

It's true that if you're doing it in a loop for say the numbers from 1 to 1e9,
calling factor() could be a little slower, but the best approach there as you
say would be to use a pre-built list of primes and use it only once, not
calling factor() at all. It would be like a prime sieve except instead of
removing all multiples of a prime, one would be marking that prime as a factor
for all its multiples. The emphasis on bigger n for factor() is conscious to
allow for scalable code over the whole range, following the recent extension a
month ago to handle uint64 beyond flintmax(). This is the change where that
was made:


changeset:   29983:ecbcc4647dbe
user:        Rik <rik@octave.org>
date:        Tue Aug 17 16:28:36 2021 -0700
summary:     factor.m: Overhaul function to support inputs > flintmax.


Until then I was using the calculator program that came with my Linux
installation (GNOME calculator), which does factorization on typing Ctrl-F,
but that is only for manual use not programmatic use. With the current series
of improvements in this thread, Octave's interpreted factor() is nearly as
fast as that compiled calculator's code, which is both nice and
programmatically accessible.

Patch 5 attached.


(file #51937)
    _______________________________________________________

Additional Item Attachment:

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



    _______________________________________________________

Reply to this item at:

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

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