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

[Hendrik K]

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

I do not have any special interest moving existing Octave code to C++ and I am
not even particularly good in C++.

I only did this for my octave project because I do there immense number
crunching and extensive back- and stress-testing which relies on the intensive
usage of permutations and combinations. Or I run into performance problems, so
I solved this via C++ in the beginning via special fit for purpose C++
routines.

Then I realized that the community could benefit from these improvements as
well, so I generalized the functions (e.g. made it octave compatible
supporting all data types, go beyond the typical usage range etc.) and entered
a bug report. 



Note that with the changes to V2 (long double) the answers are actually
correct even in extreme cases as a long double has 79 bits (e.g. on a normal
PC). So the statement that ones loses up to 11 bits of accuracy is not
correct.

- Everything providing and receiving a double and which can be represented
without loss (so flintmax) is 100% correct (using double beforehand could
result in +-1 difference due to double rounding but e.g. in my case I am
really far way from flintmax so I did not even realize this beforehand in my
original implementation).
 
For results larger than flintmax, there is a loss of precision by the nature
of a double, hence the warning in nchoosek.
 
- If one provides an uint64 type, type the answer will be uint64 and 100%
correct until saturation is reached (current nchoosek behavior : result may
have saturated at intmax)

The only remaining issues are what I would call cosmetic/display: values shown
by nchoosek.cc beyond flintmax when providing too large double values may look
differently in certain cases, but in subsequent processing will numerically
give the same results. 

The warning in nchoosek is given with reason: Actual Octave Use cases relying
on correct results beyond flintmax will need to move to octave symbolic or use
e.g. python which supports fast arbitrary-precision integers anyway or accept
the precision loss. 


     
@Arun-
My project does not use sets, but thanks for the information. And I do not
object if this bug is closed. Sorry for any inconvenience this may have
caused.


    _______________________________________________________

Reply to this item at:

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

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