[Octave-bug-tracker] [bug #65238] Improve nchoosek.m algorithm to prevent numerical issues

[Hendrik K]

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

                 Summary: Improve nchoosek.m algorithm to prevent numerical
issues 
                   Group: GNU Octave
               Submitter: koerhen
               Submitted: Thu 01 Feb 2024 07:48:20 AM 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: GNU/Linux
           Fixed Release: None
         Planned Release: None


    _______________________________________________________

Follow-up Comments:


-------------------------------------------------------
Date: Thu 01 Feb 2024 07:48:20 AM UTC By: Hendrik K <koerhen>
The current algorithm for nchoosek prevents as much as possible numerical
overflow issues by building the greatest common denominator between all
individual factors and divisors in a loop. Moreover it uses a further tweak to
take out upfront the common factor 2 for performance reasons.

This can be improved by 
i) using a smart iterative algorithm to prevent potential overflows as long as
possible.
ii) Working with the greatest common denominator only when required. 

Result: 
 - Performance is improved by about a factor 2 and
 - The (subjective) code readability is improved.


+verbatim+
tic; for i=1:5; for j=1:500; a = nchoosek(15,i); endfor; endfor;
toc;-verbatim-

Existing algorithm: ~0.14 seconds
Improved algorithm: ~0.07 seconds

A patch is attached.









    _______________________________________________________
File Attachments:


-------------------------------------------------------
Name: nchoosek_V0.patch  Size: 3KiB
<http://savannah.gnu.org/bugs/download.php?file_id=55655>

    AGPL NOTICE

These attachments are served by Savane. You can download the corresponding
source code of Savane at
https://git.savannah.nongnu.org/cgit/administration/savane.git/snapshot/savane-ac08333713703683044d24ec7abb40a5e5cb9e32.tar.gz

    _______________________________________________________

Reply to this item at:

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

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