▼
Posts: 59
Threads: 3
Joined: Oct 2010
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.
It seems to me that these new line of calculators all share the same code.
Fortunately for the ELW506, I have a workaround as it has the SUM capability:
nCr = 10^(SUM(x=A downto AB+1, logX)  SUM(X=1 to B, logX)),
or as per 506 display:
/ AB+1 B \
( SUM (logX, 1)  SUM (logX) )
\ X=A X=1 /
10
where A = n and B = the lesser of r or nr. This can then be stored in a formula memory for future use. This formula was adapted from Eamonn's "Updated HP25 C(n,r) program", message 17 in this thread. Unfortunately HP seems to have only purchased a subset of these functions for the 300s and does not contain the SUM function. .
Edited to fix a small typo
Edited: 14 Oct 2010, 10:07 a.m. after one or more responses were posted
▼
Posts: 306
Threads: 3
Joined: Sep 2009
Quote:
Fortunately for the ELW506, I have a workaround as it has the SUM capability:
Huh? If you're talking about this calculator, I'm pretty sure it does not have the sum capability. Maybe this one does, though.
But the 506w does use Simpson's rule for evaluating integrals, so it can be manipulated into performing sums:
The funny (ba)/2 argument in the integrals is the third argument you give the integrator, the one that indicates how many applications of Simpson's rule are to be used.
Obviously that's a pretty complicated formula, but if ba is large enough it can save some time as compared to entering the sums manually.
▼
Posts: 59
Threads: 3
Joined: Oct 2010
Hi Crawl,
I'm talking about this calculator, note that the W is before the 506. A small difference in model no., but quite a different calculator :)
May be there's a difference in model no.'s for US and EU release, the ELW516B being the US equivalent of ELW506?
▼
Posts: 1,545
Threads: 168
Joined: Jul 2005
Define "allowable" values. If the nCr or nPr functions are done using the x! function, allowable values will not include the 200.
▼
Posts: 59
Threads: 3
Joined: Oct 2010
Hi Gene,
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 :).
▼
Posts: 1,545
Threads: 168
Joined: Jul 2005
Good. that's why I asked the question. I know some calculators use algorithms that do not use the x! but that some from long ago did.
Definitely an "oops" given the stated allowed values in the documentation.
Posts: 59
Threads: 3
Joined: Oct 2010
Hi Crawl,
Nice idea for that calc. As the ELW506 seems to implement the same integration technique, I'm going to go away and look at implementing your formula. Don't hold your breath, this may take me a while  I'm no maths guru :).
Edited after implementing Crawl's formula on the ELW506
OK, that works!!
For the first sum in my formula, I used a=AB+1 and b=A in yours
For the second sum in my formula, I used a=1 and b=B in yours
I saved the first and second parts of the formula in separate memories as I get a "buffer full" error when trying to put the whole lot on one line. Store each result in a memory (e.g. C and D) and take 10^(CD). A few steps, but doable.
Reverse engineering integration, cool!
Edited: 14 Oct 2010, 12:02 p.m.
Posts: 2,448
Threads: 90
Joined: Jul 2005
did you use a wacom tablet for that writing of yours?
Posts: 528
Threads: 40
Joined: Dec 2008
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.
In (untested) pseudoCcode, it looks like this:
comb(n,r)
{
if (r > nr) r = nr; // get the smaller of r and nr
result = nc+1;
f = result+1; // the next factor
for (d = 2 to r) {
result = result * f;
result = result / d; // do the * and / in the right order!
++f;
}
return result;
}
The first 2 lines in the "for" loop could be combined into result = result * f / d, but I split them apart to stress that the multiply must come first.
Dave
▼
Posts: 59
Threads: 3
Joined: Oct 2010
Hi Dave,
Yes, I have often implenemted similar product iterative routines in BASIC on old Sharp programmables (PC1251 etc.). However the ELW506 does not have programming nor does it have a PRODUCT function, the only iterative function is the SUM function (and integrate function as pointed out by Crawl), thus I had to devise a way to use that. The accuracy of the results have been satisfactory so far.
e.g.
Inputs ELW506 using Formula Wolfram Alpha
90C7 7471735560 7471375560
101C6 1267339920 1267339920
70C8 9440350920 9440350920
425C23 5.987299533E37 5.9872995328217166490998168... × 10^37
200C55 7.718340811E49 7.7183408114309579595976889... × 10^49
335C167 3.044358792E99 3.04435879314697921045998279... × 10^99
Unfortunately I wanted to use combinatorials in another SUM function, but as I cannot use a SUM within a SUM, and I can't find a way of using a stored formula within another formula (on the ELW506), so I'm back to programmable calculators :(.
Edit:
Dave Hayden said
Quote:
So after each division, you've computed a different nCr which is guaranteed to be an integer.
The Sum function of course will always use the integer of any of its arguments (e.g. Sum X, X=1 to 5.8 will still produce 15), this may one the reasons for the reasonably good accuracy demonstrated above.
Edited: 2 Nov 2010, 1:07 p.m.
Posts: 1,792
Threads: 62
Joined: Jan 2005
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.
▼
Posts: 735
Threads: 34
Joined: May 2007
Quote:
C(200,44) = 3.97106E44 was returned; C(200,45) = 1.37664E45 was not  "Error" instead.
Since P(200, 44) = 1.0556E99 and P(200, 45) = 1.6468E101 I assume the following
formula is used:
C(n, r) = P(n, r)/r!
Best regards
Thomas
BTW: Using the HP 35s I get an OVERFLOW for P(422, 200) but still
the correct result for C(422, 200) = 2.3720E125. This shows it can be
done correctly.
Edited: 17 Oct 2010, 4:57 a.m.
▼
Posts: 1,792
Threads: 62
Joined: Jan 2005
Quote:
(On the Casio fx115MS and fx115ES, and the Sharp EL520R): C(200,44) = 3.97106E44 was returned, but C(200,45) = 1.37664E45 was not  "Error" instead.
Since P(200, 44) = 1.0556E99 and P(200, 45) = 1.6468E101 I assume the following formula is used:
C(n, r) = P(n, r)/r!
Thomas (and Marcus von Cube) 
Yes, that would seem to be the basis of the 'misperformance' of these and other models. The implementation on the Casios is not purely "C(n,r) = P(n,r)/r!", as they correctly (and quickly) calculate C(71,70) = 71, despite that both P(71,70) and 70! exceed 1E100. They will solve up to C(120,70) = 1.83617E34, but not C(121,70) = 4.35641E34.
The Sharp fails to calculate C(71,70), giving an "Error 2" message, so it probably does use "C(n,r) = P(n,r)/r!" directly.
This example underscores the differences in product development and marketing between quality calculators and some modern ones. If algortihmic shortcomings such as this one had appeared in the costly HP models of yesteryear, professional engineers and scientists would have complained. Flaws were actually quite rare, because HP had invested the effort and financial commitment (paying many highlyskilled people) to implement robustness in their legacy products.
Young students are less likely to need to tackle 'extreme' or difficult mathematical problems, won't care if the calc comes up short, and for $15, how much can be expected, anyway?
On language: "misperform" may not appear in your dictionary, but apparently several modern unabridged versions include it. "Misperform" and "misperfomance" sound unawkward and would not mean the same as "malfunction" or "misoperate".
 KS
Edited: 17 Oct 2010, 3:32 p.m. after one or more responses were posted
▼
Posts: 735
Threads: 34
Joined: May 2007
Quote:
They will solve up to C(120,70) = 1.83617E34, but not C(121,70) = 4.35641E34.
Interesting! Probably C(120, 50) and C(121, 51) are calculated
instead: as P(120, 50) = 5.5846E98 and P(121, 51) = 6.7573E100
which leads to an OVERFLOW.
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
I found a hint in the fx5800P manual (page E130):
Function : Input Range
nPr : 0<=n<1E100, 0<=r<=n (n, r are integers), 1<=n!/(nr)!<1E100
nCr : 0<=n<1E100, 0<=r<=n (n, r are integers), 1<=n!/r!<1E100 or 1<=n!/(nr)!<1E100
So it works according to specifications.
▼
Posts: 59
Threads: 3
Joined: Oct 2010
Interesting, the Sharp ELW506 manual states for nCr : n!/(nr)!<1E100
However, the 300s manual states for nCr : 1<=n!/(r!(nr)!)<1E100. As this is the definition of combinatorials, I interpreted this to be equivalent to "answer".
The notsocheap EL9900 only states "0 <= r <= n <= 69" for both nPr and nCr. Considering it's supposed to be competing in the market with other graphics calculators, it's a bit of a let down. It is fully programmable though, but as I call the routine from another iterative program, execution times escalate quickly.
Posts: 3,229
Threads: 42
Joined: Jul 2006
My 34s firmware calculates both permutations and combinations using the LnGamma function so overflow really isn't a concern until the final exponential step. Thus all these cases work fine :)
In fact, the firmware handles the extension of both of these functions to the complex plane. And yes, special care is taken to ensure that integer arguments produce an integer result.
 Pauli
Posts: 3,283
Threads: 104
Joined: Jul 2005
Karl, the not so cheap Casio fx5800P fails in the same way. Thomas assumption that C(n,r) = P(n,r)/r! seems to be correct for all modern Casios.
Edit: This seems to be common to many "Casioish" calculators like the older Casio fx991s and the new "Rex Dual Power" calculator sold at Aldi Süd in Germany recently.
Edit2: I tried it with the HP9G and 30s: They do not fail on C(200,45). The Casio CFX985G fails while the fx9860G slim does not fail. Casio seems to have corrected it at least for part of their offerings.
Edit3: All the Casio BASIC pockets (with the respective functionality) fail on NCR(200,45) but can compute NCR(200,44)
Edited: 17 Oct 2010, 2:03 p.m.
Posts: 306
Threads: 3
Joined: Sep 2009
Another way of approaching this would be to use Sterling's approximation,
ln n! ~ n ln n  n + 1/2 ln (2 pi n)
This, however, only gets you
7.73 x 10^49
So you get the correct order of magnitude, and 2 correct digits, but the rest are wrong.
You might be able to try more terms in the expansion, but I imagine few want to memorize more terms.
Posts: 764
Threads: 118
Joined: Aug 2007
Here is the 12c Version for nCr.
Store n in R1 and r in R2
Registers used:
R3 = sum of the left term
R4 = sum of the right term
R5= b. (r or nr whichever is smaller)
R6= ab+1
R7 = counter
Program:
1. 1
2. STO 7
3. 0
4. STO 3
5. STO 5
6. RCL 1
7. RCL 2
8. 
9. RCL 2
10. x<=y
11. GTO 13
12. GTO 15
13. RCL 2
14. GTO 18
15. RCL 1
16. RCL 2
17. 
18. STO 5
19. CHS
20. RCL 1
21. +
22. 1
23. +
24. STO 6
25. RCL 6
26. LN
27. 1
28. 0
29. LN
30. /
31. STO+ 3
32. 1
33. RCL 6
34. +
35. STO 6
36. RCL 1
37. RCL 6
38. x<=y
39. GTO 25
40. RCL 7
41. LN
42. 1
43. 0
44. LN
45. /
46. STO+ 4
47. 1
48. RCL 7
49. +
50. STO 7
51. RCL 5
52. RCL 7
53. x<=y
54. GTO 40
55. RCL 3
56. RCL 4
57. 
58. 1
59. 0
60. x<>y
61. y^x
62. GTO 00
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
A better readable version of the above:
Here is the 12c Version for nCr.
Store n in R1 and r in R2
Registers used:
R3 = sum of the left term
R4 = sum of the right term
R5= b. (r or nr whichever is smaller)
R6= ab+1
R7 = counter
Program:
1. 1
2. STO 7
3. 0
4. STO 3
5. STO 5
6. RCL 1
7. RCL 2
8. 
9. RCL 2
10. x<=y
11. GTO 13
12. GTO 15
13. RCL 2
14. GTO 18
15. RCL 1
16. RCL 2
17. 
18. STO 5
19. CHS
20. RCL 1
21. +
22. 1
23. +
24. STO 6
25. RCL 6
26. LN
27. 1
28. 0
29. LN
30. /
31. STO+ 3
32. 1
33. RCL 6
34. +
35. STO 6
36. RCL 1
37. RCL 6
38. x<=y
39. GTO 25
40. RCL 7
41. LN
42. 1
43. 0
44. LN
45. /
46. STO+ 4
47. 1
48. RCL 7
49. +
50. STO 7
51. RCL 5
52. RCL 7
53. x<=y
54. GTO 40
55. RCL 3
56. RCL 4
57. 
58. 1
59. 0
60. x<>y
61. y^x
62. GTO 00
▼
Posts: 764
Threads: 118
Joined: Aug 2007
Thanks, Marcus. :)
I have to remember to do the HTML code.
Edited: 31 Oct 2010, 11:11 a.m.
