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

[Hendrik K]

Follow-up Comment #2, bug#65238 (group octave):

Changes are fine.

Is there a reason why the multiplication and division is done in two steps for
the "default case" (lines 145-146), but it is done in one step for the "large
number case" (line 138)?

--> Mathematical there is no difference but numerical there is especially for
integer: 
a) In the default case (v - k + i) is not always divisible by i, but C * (v -
k + i) is always divisible by i. So the order and the number of the two steps
is important in order to avoid numerical issues.

b) In the "large number case" we determine the gcd beforehand between C and i
((g1)), then the gcd between (v - k + i) and (i / g1) ((g2)). So C is
divisible by g1 by design and we can do this without any numerical issue.
Then we can multiply by the smallest remaining possible factor (v - k +
i)/g2.
Note that then C still needs be divided by (i / (g1 * G2)) when doing the math
(and in the code) but in practice it should be 1 until saturation/flintmax.
But as we go beyond flintmax, we should better keep the final division.

 

Is your name and email in the patch still correct?
--> Yes except that I am written with "oe" and not "ö".

Does the commit message correctly describe the change?
--> Yes

Could I add you to the list of contributors that appears at the beginning of
the manual? https://docs.octave.org/latest/Acknowledgements.html
--> Yes


    _______________________________________________________

Reply to this item at:

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

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