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

[anonymous]

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

I'm attaching Patch 4 and an updated factor.m to this comment. This version is
much faster (4x) than previous versions by changing the sequence of divisions
and using the same type everywhere, getting rid of repeated type conversions.
It consistently pulls out factors in ascending order, making the final sort
unnecessary. I also moved the division routines to an internal function that's
simply called twice, once for smallprimes and once for largeprimes without a
loop in the main function body.

Re the structure of Patch 2, it's generally a bad idea to stick an if(i) or a
switch(i) statement inside a deterministic "for i" loop. That is the for-case
antipattern, also called the loop-switch sequence
(https://en.wikipedia.org/wiki/Loop-switch_sequence), especially because the
"for i = 1:2" loop in Patch 2 is fully deterministic without depending on
external input. I consciously avoided that structure in Patch 3 and Patch 4.

Re the repeated division of smallprimes in the second round in Patch3, that
was a test I had already done before making Patch 3, but doing that test and
filter was slower than simply dividing it. I removed it before attaching Patch
3. In Patch 4, I've added comments to show what has been tested and what
future programmers should look to tweak, especially tests about persistent
variables and parameter ranges.

Attachments: Patch4 and factor.m with Patch4 applied.

Passes all Octave checks in "make check".


(file #51925, file #51926)
    _______________________________________________________

Additional Item Attachment:

File name: factor.m                       Size:7 KB
    <https://file.savannah.gnu.org/file/factor.m?file_id=51925>

File name: patch4                         Size:5 KB
    <https://file.savannah.gnu.org/file/patch4?file_id=51926>



    _______________________________________________________

Reply to this item at:

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

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