Permutations & Combinations for large inputs

[Dave Britten]

(05-26-2015 09:26 AM)Dieter Wrote:  Dave, your method requires just one single overflow test: If n! does not overflow, the smaller values (n–r)! and r! won't either.

Yeah, those can probably go. I'm just hard-wired for defensive coding when it comes to error trapping.

(05-26-2015 09:26 AM)Dieter Wrote:  So lines 17,19 and 20 resp. 25, 27 and 28 can be removed. They should be removed because a set flag 25 may cover other errors, e.g. non-integer or negative arguments.

In this case, it shouldn't be terribly harmful. The worst that will happen is it will detect some other error condition and run the looping algorithm instead. But on a related note, you should (nearly) always test flag 25 with FC?C so as not to accidentally leave it set and mask an error later.

(05-26-2015 09:26 AM)Dieter Wrote:  Just for comparison, here is another version that does not require any data registers and runs faster due to two separate loops and some further improvements within these. For instance two counters are used that are set up before the loops start so that no additional arithmetics within the loops are required. Both loops can be combined to one, but in this case especially nPr would run slower. The program also uses the property Comb(n,r) = Comb(n, n–r), which substantially speeds up the program for r > n/2. Flag 25 is not used – checking whether n>69 will do.

Good idea with doing multiple loops. It briefly crossed my mind, but I wasn't sure which would be faster on the 41, and hadn't tested it yet.

(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...:
- 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))

Mine deals with the first two situations, since it tries factorials first, and switches to looped division/multiplication if that overflows. As for r=0 or r>n, I haven't done anything to detect those. Sometimes you just have to accept garbage in garbage out.