Permutations & Combinations for large inputs
|
05-26-2015, 12:22 PM
Post: #4
|
|||
|
|||
RE: Permutations & Combinations for large inputs
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...: - C(335,167) overflows while the result is < 1e100 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). - C(n,0) = 1 - C(n,n-1) = C(n,1) solution: calculate C(n,min(p,n-p)) The following routine avoids these, but may return slightly inaccurate results > 1e10 due to roundoff. Nothing to be done about that. Code: L X Y Z T 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 2 Guest(s)