[MORE] HP300s cannot do nCr for many allowable values Message #11 Posted by Karl Schneider on 16 Oct 2010, 12:22 a.m., in response to message #1 by DeboT
Quote:
The HP300s cannot do nCr for many allowable values
E.g. 200C55 = 7.718340811E49 gives an error on the 300s. Similarly on the Casio fx85GT plus, and Sharp ELW506.
...
For "allowable" values I mean what the manual states:
0<n<=1E10; 0<r<n; 1<=answer<1E100
Just because the definition of combinatorial includes factorials, it doesn't mean the implemented algorithm should be limited to that.
Try it on an HP11C for instance. As long as the answer <1E100 I have not found a (n,r) that it can't find an answer for.
Also the 300s happily calculates 200C40 :).
I got exactly the same results for the 'cheapo' (< $20 each) Casio fx115MS and fx115ES, and the Sharp EL520R: C(200,44) = 3.97106E44 was returned; C(200,45) = 1.37664E45 was not  "Error" instead. It seems as though the same algorithms are being used.
This misperformance ought not to happen, but then again, consider the typical customer and retail price of most modern calculators.
Absolutely, if the inputs to a function are within the pertinent domain of the calculator, and the output of the function is within its range, the answer correct to its supported number of significant digits should be returned. That's all there is to it.
The two valid inputs to statistical combination C(n,r) are nonnegative integers, so they must be identifiable as such. For a 10digit calculator, 999,999,999 (1E10  1) would be the upper limit of input, and 9.999999999E99 would be the maximum output.
So, I would state:
0 <= n < 1E10; 0 <= r <= n; 1 <= answer < 1E100
A smart algorithm for combination or permutation, after validating both inputs, will achieve the following:
 Limit the magnitude of the intermediate results during calculation to prevent unnecessary overflow
 Calculate the result with the minimum number of operations
 Identify a true overflow condition as quickly as possible
 Minimize roundoff error
An approach was suggested in this thread:
nCr program  MCODE
David Hayden stated:
Quote:
If you're going to iterate, then you can do it with multiplication and division in such a way that you never get a fractional result. So this may be faster and/or more accurate.
I'll demonstrate with an example. Consider 9C4 = (6*7*8*9)/(2*3*4) If you compute this as 6*7/2*8/3*9/4 then the intermediate results are guaranteed to be integers. To see this consider:
6*7/2 = 7C2
*8/3 = 8C3
*9/4 = 9C4
So after each division, you've computed a different nCr which is guaranteed to be an integer.
It is true that each intermediate result calculated in this manner is guaranteed to be an integer. Another way to view it is as follows: When the first two consecutiveinteger numerands are multiplied together, one of them must be even; when the third numerand is multiplied, one of the first three must be divisible by three, and so forth.
However, I doubt that there is any value to integervalued intermediate results unless (faster) integer arithmetic is performed. Also, multiplying before dividing will eventually cause an overflow for some computations.
To prevent overflow at intermediate points, each term  consisting of a quotient of two integers  should be calculated prior to multiplying. The magnitude of the quotient terms should monotonically decrease, but always remain above unity, so the final result need not be obtained by 'scaling down' the running product.
Extendedprecision floatingpoint calculations throughout may eliminate most roundoff error. Then, as a final step, the result could be rounded to the nearest integer  if it is within the calculator's displayable range of integers.
 KS
Edited: 17 Oct 2010, 12:51 a.m.
