Changeset 42494 for branches/eam_branches/ipp-20230313/psLib/src/math/psBinomialCoeff.c

Timestamp:

Aug 15, 2023, 12:09:10 PM (3 years ago)

Author:

eugene

Message:

psBinomialCoeff had an error : the multiplicative formula was using an integer value to carry the intermediate results, but those were sometimes fractional

File:

• branches/eam_branches/ipp-20230313/psLib/src/math/psBinomialCoeff.c (modified) (1 diff)

branches/eam_branches/ipp-20230313/psLib/src/math/psBinomialCoeff.c

@@ -22 +22 @@
   if (k == 0) { return (b); }
 
+  psS64 num = 1;
+  psS64 den = 1;
+
   for (i = 1; i <= k; i++) {
-    b *= (N - (k - i))/i;
+
+      // old version: b *= (N - (k - i))/i;
+      // wikipedia recursion version: b *= (N + 1 - i)/i;
+
+      // the old version just counts the elements in the opposite order from the wikipedia version:
+
+      // numerators would be, e.g., for C(6,4):
+      // old  version (6 - (4 - 1)), (6 - (4 - 2)), (6 - (4 - 3)), (6 - (4 - 4)) = 3, 4, 5, 6
+      // wiki version (6 + 1 - 1), (6 + 1 - 2), (6 + 1 - 3), (6 + 1 - 4) = 6, 5, 4, 3
+
+      // denominators would be the same: 1, 2, 3, 4.
+
+      // since these are multiplied, the order of the numerators is independent of the order of the denominators
+
+      // but both of these formulae are bad because the factors can be fractional, but that means we cannot use an
+      // integer to carry the intermediate result.  
+
+      // instead, we need to calculate the integer product of the denominators and the integer
+      // product of the numerators and divide at the end
+      
+      num *= (N + 1 - i);
+      den *= i;
   }
+
+  b = num / den;
 
   return(b);