[Octave-bug-tracker] [bug #63992] nchoosek has suboptimal performance

[Hendrik K]

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

To wrap this up, I attach the final nchoosek.cc patch for people stumbling
over this bug and having performance issues.

 
The patch is a 100% like for like replacement of the current nchoosek without
any known limitation. 

Advantages:
a) Performance is 50(!) times faster. 

tic; for i=1:25; for j=1:100; a = nchoosek(50,i); endfor; endfor; toc;

Native version:  0.35475 seconds 
C++ version:     0.006248 seconds

b) Through the internal usage of long doubles, the precision of very large
results beyond flintmax will be better.


Enjoy


Note 1: For higher n the performance gain will even higher by avoiding
calculating the common denominator calculation (O(log(max(n,k)) effort).
Instead the C++ program uses a double long and a smart algorithm.

Note 2: Compared to the initial test in submission 1, this version is now
really materially faster: the original version used the octave interpreter in
C++ to determine flintmax and to cast the final result. This is now done
directly using C++ methods which was the major bottleneck.

(file #54562)

    _______________________________________________________

Additional Item Attachment:

File name: nchoosek_Final                 Size:25 KB
    <https://file.savannah.gnu.org/file/nchoosek_Final?file_id=54562>



    _______________________________________________________

Reply to this item at:

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

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