Permutations & Combinations for large inputs

[Dieter]

(05-26-2015 12:22 PM)Werner Wrote:  Common pitfalls for a COMB routine:
- C(8,3) calculated as 8/3*7/2*6 returns 56.00000001
solution : calculate it as 8/1*7/2*6/3, guaranteeing integers all along, but then...:

That's the way I do it in higher-level programming languages where count-up loops are much more relaxed than on calculators like the HP41. ;-) However, small input like in your example is evaluated directly via factorials in the program I posted. Since the program calculates n!/(n–r)! first (which always is an integer) the results should be exact here.

(05-26-2015 12:22 PM)Werner Wrote:  - C(335,167) overflows while the result is < 1e100

OK. But at least the version I posted correctly retuns C(336, 168) as 6,0887 E+99. #-)

(05-26-2015 12:22 PM)Werner Wrote:  solution: calculate 0.001*n/1*(n-1)/2*(n-2)/3... *1000
1e3 is large enough because we are looking for the largest p for which C(n,p)<1e100,
and that is 168 (C(336,168) = 6e99)
The largest intermediate number formed is p*C(n,p).

That's an interesting approach.

(05-26-2015 12:22 PM)Werner Wrote:  - C(n,0) = 1
- C(n,n-1) = C(n,1)
solution: calculate C(n,min(p,n-p))

That's what my version implements as well. However, the C(n, 0) case has to be handled separately. I now posted an update.

(05-26-2015 12:22 PM)Werner Wrote:  The following routine avoids these, but may return slightly inaccurate
results > 1e10 due to roundoff. Nothing to be done about that.

Yes, you can't expect 10-digit accuracy with merely 10-digit precision.

Dieter