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

[anonymous]

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

Patch 2 is good at the low end, for 1 <= n <= 1e6 (execution times are 0.16
milliseconds or less).

Patch 1 scales much better for n >= 10e9 (execution times are 0.3 milliseconds
and longer).

I've made a new Patch 3 that incorporates aspects of both Patch 1 and Patch 2,
switching to the faster algorithm based on input value. Feel free to improve
it.

For the low end (all values from 1 to 1e6), the Base version takes 154
microseconds for each factorization on average, Patch 3 takes 164
microseconds, and Patch 2 takes 123 microseconds.

As n increases, Patch 3 takes over, reducing 33-second runtimes with the Base
version to 0.3 seconds, and that 100-fold saving in time is absolutely worth
the 10-microsecond penalty at the low end.

For background, the reason I was motivated to speed up factor() was when I
tried to factorize the number 429632517266727264, which was the number of
solutions to 4-coloring a certain graph. The base version of factor() took
10.85 seconds. Both Patch1 and Patch2 finish it off in 43 milliseconds, now
Patch3 as well. The rationale is therefore to emphasize speeding up execution
for n >= 1e14, because smaller numbers really don't take much time to
factorize (sub-millisecond up to 1e9 or 1e10).

I did a stratified sampling with 1600 data points spread over 16 orders of
magnitude with 100 data points each. Raw data attached. Time information
attached as two graphs, plotting the median execution time for each order of
magnitude. In both graphs, the black circles are the Base time, the blue dots
are Patch1, the red plus signs are Patch2 and the green asterisks are Patch3.

Regarding the failed assertions for Patch2, it's because Patch2 is returning
doubles for some reason in some cases, so the product loses precision even if
the prime factors are smaller than flintmax:


octave:29> foo = uint64 (33333333333333338)
foo = 33333333333333338


octave:32> myfactor(foo)
ans =
                2               29  574712643678161

octave:33> class(myfactor(foo))
ans = uint64
octave:34> prod(myfactor(foo),"native") 
ans = 33333333333333338
octave:35> prod(myfactor(foo),"native") == foo
ans = 1


octave:36> myfactor2(foo)
ans =
                       2                      29         574712643678161

octave:37> class(myfactor2(foo))
ans = double
octave:38> prod(myfactor2(foo),"native") 
ans = 3.333333333333334e+16
octave:39> prod(myfactor2(foo),"native") == foo
ans = 0


octave:40> prod(uint64(myfactor2(foo)),"native") == foo   ## extra cast to
uint64 fixes it
ans = 1



(file #51913, file #51914, file #51915, file #51916)
    _______________________________________________________

Additional Item Attachment:

File name: patch3                         Size:1 KB
    <https://file.savannah.gnu.org/file/patch3?file_id=51913>

File name: factorout                      Size:76 KB
    <https://file.savannah.gnu.org/file/factorout?file_id=51914>

File name: factorperflog.png              Size:90 KB
    <https://file.savannah.gnu.org/file/factorperflog.png?file_id=51915>

File name: factorperflinear.png           Size:56 KB
    <https://file.savannah.gnu.org/file/factorperflinear.png?file_id=51916>



    _______________________________________________________

Reply to this item at:

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

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