The Museum of HP Calculators

HP Forum Archive 19

[ Return to Index | Top of Index ]

HP-300s cannot do nCr for many allowable values
Message #1 Posted by DeboT on 14 Oct 2010, 7:36 a.m.

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


where A = n and B = the lesser of r or n-r.

This can then be stored in a formula memory for future use.

This formula was adapted from Eamonn's "Updated HP-25 C(n,r) program", message 17 in this thread.

Unfortunately HP seems to have only purchased a sub-set 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

      
Re: HP-300s cannot do nCr for many allowable values
Message #2 Posted by Crawl on 14 Oct 2010, 9:08 a.m.,
in response to message #1 by DeboT

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.

            
Re: HP-300s cannot do nCr for many allowable values
Message #3 Posted by DeboT on 14 Oct 2010, 9:38 a.m.,
in response to message #2 by Crawl

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?

                  
Re: HP-300s cannot do nCr for many allowable values
Message #4 Posted by gene wright on 14 Oct 2010, 10:27 a.m.,
in response to message #3 by DeboT

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

                        
Re: HP-300s cannot do nCr for many allowable values
Message #5 Posted by DeboT on 14 Oct 2010, 10:40 a.m.,
in response to message #4 by gene wright

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

                              
Re: HP-300s cannot do nCr for many allowable values
Message #6 Posted by gene wright on 14 Oct 2010, 11:20 a.m.,
in response to message #5 by DeboT

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.

            
Re: HP-300s cannot do nCr for many allowable values
Message #7 Posted by DeboT on 14 Oct 2010, 10:45 a.m.,
in response to message #2 by Crawl

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.

            
OT did you use a wacom
Message #8 Posted by bill platt on 15 Oct 2010, 7:22 p.m.,
in response to message #2 by Crawl

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

      
Re: HP-300s cannot do nCr for many allowable values
Message #9 Posted by David Hayden on 14 Oct 2010, 6:04 p.m.,
in response to message #1 by DeboT

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) 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;
}
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

            
Re: HP-300s cannot do nCr for many allowable values
Message #10 Posted by DeboT on 15 Oct 2010, 5:50 a.m.,
in response to message #9 by David Hayden

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


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 EL-W506), 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.

      
[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

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.

            
Re: [MORE] HP-300s cannot do nCr for many allowable values
Message #12 Posted by Thomas Klemm on 17 Oct 2010, 4:56 a.m.,
in response to message #11 by Karl Schneider

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.

                  
Implemented methods for caclulating nCr
Message #13 Posted by Karl Schneider on 17 Oct 2010, 2:20 p.m.,
in response to message #12 by Thomas Klemm

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

                        
Re: Implemented methods for caclulating nCr
Message #14 Posted by Thomas Klemm on 17 Oct 2010, 3:25 p.m.,
in response to message #13 by Karl Schneider

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.

                              
Re: Implemented methods for caclulating nCr
Message #15 Posted by Marcus von Cube, Germany on 17 Oct 2010, 4:45 p.m.,
in response to message #14 by Thomas Klemm

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.

                                    
Re: Implemented methods for caclulating nCr
Message #16 Posted by DeboT on 18 Oct 2010, 7:10 a.m.,
in response to message #15 by Marcus von Cube, Germany

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.

            
Re: [MORE] HP-300s cannot do nCr for many allowable values
Message #17 Posted by Paul Dale on 17 Oct 2010, 5:37 a.m.,
in response to message #11 by Karl Schneider

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

            
Re: [MORE] HP-300s cannot do nCr for many allowable values
Message #18 Posted by Marcus von Cube, Germany on 17 Oct 2010, 1:12 p.m.,
in response to message #11 by Karl Schneider

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.

      
Re: HP-300s cannot do nCr for many allowable values
Message #19 Posted by Crawl on 18 Oct 2010, 11:52 a.m.,
in response to message #1 by DeboT

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.

      
Re: HP-300s cannot do nCr for many allowable values
Message #20 Posted by Eddie W. Shore on 29 Oct 2010, 3:54 p.m.,
in response to message #1 by DeboT

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

            
Re: HP-300s cannot do nCr for many allowable values
Message #21 Posted by Marcus von Cube, Germany on 30 Oct 2010, 2:32 p.m.,
in response to message #20 by Eddie W. Shore

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
                  
Re: HP-300s cannot do nCr for many allowable values
Message #22 Posted by Eddie W. Shore on 31 Oct 2010, 11:10 a.m.,
in response to message #21 by Marcus von Cube, Germany

Thanks, Marcus.  :)  
I have to remember to do the HTML code.

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

[ Return to Index | Top of Index ]

Go back to the main exhibit hall