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

[anonymous]

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

                 Summary: Performance of factor(). Proposed patch attached.
                 Project: GNU Octave
            Submitted by: None
            Submitted on: Wed 08 Sep 2021 07:32:42 PM UTC
                Category: Octave Function
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Performance
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
                 Release: dev
         Discussion Lock: Any
        Operating System: Any

    _______________________________________________________

Details:

The function factor() could be much faster for certain large inputs. This was
discovered in the following real-world case:


T = uint64(429632517266727264)
tic; factor(T), toc
tic; factor(T / 2^5), toc
tic; factor(T / 2^5 / 3^3), toc


The time performance is respectively:

Elapsed time is 9.79291 seconds.
Elapsed time is 0.869242 seconds.
Elapsed time is 0.112411 seconds.


A more pathological case is this:


T = uint64(6) ^ 62
tic; factor(T), toc
tic; factor(T / 2^5), toc
tic; factor(T / 2^10), toc


which takes respectively


Elapsed time is 42.4696 seconds.
Elapsed time is 6.06825 seconds.
Elapsed time is 0.526102 seconds.


The bottleneck seems to be in the calculation of all prime numbers up to
sqrt(n) inside scripts/specfun/factor.m, even if n is divisible by small
numbers like 2 or 3. This suggests a special-case workaround like: repeatedly
divide n by 2, then repeatedly by 3, and the resulting number which has
neither 2 nor 3 as a factor can be passed off to the existing code. This
results in a 10x to 80x speedup at the cost of some lines of extra code. This
can be extended to other small primes like 5 and 7 but with diminishing
returns. Question to the developers: is this performance worth the extra code?
If so, a proposed patch to factor.m is attached.




    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Wed 08 Sep 2021 07:32:42 PM UTC  Name: factor.m.patch  Size: 970B   By:
None

<http://savannah.gnu.org/bugs/download.php?file_id=51878>

    _______________________________________________________

Reply to this item at:

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

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