|[MORE] HP-300s 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
The HP-300s cannot do nCr for many allowable values
E.g. 200C55 = 7.718340811E49 gives an error on the 300s. Similarly on the Casio fx-85GT plus, and Sharp EL-W506.
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 HP-11C 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 fx-115MS and fx-115ES, and the Sharp EL-520R: 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 non-negative integers, so they must be identifiable as such. For a 10-digit 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:
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 consecutive-integer 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 integer-valued 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.
Extended-precision floating-point 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.
Edited: 17 Oct 2010, 12:51 a.m.