HP Forums

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.

It seems to me that these new line of calculators all share the same code.

Fortunately for the EL-W506, I have a workaround as it has the SUM capability:

nCr = 10^(SUM(x=A downto A-B+1, logX) - SUM(X=1 to B, logX)),

or as per 506 display:

   / A-B+1              B        \

  (  SUM  (logX, -1) - SUM (logX) ) 

   \ X=A               X=1       /

10

Edited: 14 Oct 2010, 10:07 a.m. after one or more responses were posted

Quote:

---

Fortunately for the EL-W506, 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 (b-a)/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 b-a is large enough it can save some time as compared to entering the sums manually.

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 EL-W516B being the US equivalent of EL-W506?

Define "allowable" values. If the nCr or nPr functions are done using the x! function, allowable values will not include the 200.

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

Hi Crawl,

Nice idea for that calc. As the EL-W506 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 EL-W506


OK, that works!!


For the first sum in my formula, I used a=A-B+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^(C-D). A few steps, but do-able.

Reverse engineering integration, cool!

Edited: 14 Oct 2010, 12:02 p.m.

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.

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

In (untested) pseudo-C-code, it looks like this:

comb(n,r)

{

  if (r > n-r) r = n-r;   // get the smaller of r and n-r

  result = n-c+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;

}

Dave

Hi Dave,

Yes, I have often implenemted similar product iterative routines in BASIC on old Sharp programmables (PC-1251 etc.). However the EL-W506 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      EL-W506 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

Edit:

Dave Hayden said

Quote:

---

So after each division, you've computed a different nCr which is guaranteed to be an integer.

---

Edited: 2 Nov 2010, 1:07 p.m.

did you use a wacom tablet for that writing of yours?

Quote:

---

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:

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 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.

-- KS

Edited: 17 Oct 2010, 12:51 a.m.

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.

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

Karl, the not so cheap Casio fx-5800P 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 CFX-985G fails while the fx-9860G 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.

Quote:

---

(On the Casio fx-115MS and fx-115ES, and the Sharp EL-520R):
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 highly-skilled 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

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.

I found a hint in the fx-5800P manual (page E-130):

Function : Input Range

nPr : 0<=n<1E100, 0<=r<=n (n, r are integers), 1<=n!/(n-r)!<1E100

nCr : 0<=n<1E100, 0<=r<=n (n, r are integers), 1<=n!/r!<1E100 or 1<=n!/(n-r)!<1E100

So it works according to specifications.

Interesting, the Sharp EL-W506 manual states for nCr : n!/(n-r)!<1E100

However, the 300s manual states for nCr : 1<=n!/(r!(n-r)!)<1E100. As this is the definition of combinatorials, I interpreted this to be equivalent to "answer".

The not-so-cheap EL-9900 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.

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.

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 n-r whichever is smaller)
R6= a-b+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

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 n-r whichever is smaller)

R6= a-b+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

Thanks, Marcus.  :)  

I have to remember to do the HTML code.  

Edited: 31 Oct 2010, 11:11 a.m.