HP 12C Permutation and Combination

[grsbanks]

(08-17-2017 12:25 PM)Gamo Wrote:  Hello Dieter

Formula: mPn = m! / (m-n)!

I decided to calculate manually this way because of the rule of operation that must start from the inner most parentheses first and I have no choice to reverse the division by using 1/x since the problem start from the denominator portion of the fraction.
I believe that calculate this way give more accurate result.

Gamo

Gamo, here's a hint: LSTx

number m
n!
LSTx
number n
-
n!
/

No need to use decimals at all that way.

[Dieter]

(08-23-2017 06:40 AM)Gamo Wrote:  Your program is very nice and easy to use so I use it a lot and find out another problem with 60p5 this time the result show 655 381 440.2 on regular cheap Casio fx-260 solar gave result 655 381 440

Sure. As already explained (please read my previous posts again) this can and will happen if you calculate with factorials which cannot be represented exactly with 10 digits.

(08-23-2017 06:40 AM)Gamo Wrote:  Is it possible just to add INTG to the program?

That's not a good idea. The error can be both positive and negative. If the result is a bit too small, INTG will be off by one (or even more). Just remember 25P7 on the Prime or any other correctly working 12-digit calculator (2422727999,99) resp. on the 10-digit 12C (2422727999). You could round the result by adding 0,5 first and then use INTG, but this does not mean that the result is exact – the error may be > 1.

If you want to avoid or at least minimize this kind of error you have to do the calculation without factorials. I have described a way to do so and you'll also find an explanation why the preferable method avoids roundoff errors.

Here are two programs that will do this job.

First, here is a compact version that returns both nCr in X and nPr in Y. If you want to have it the other way round, simply swap the final RCL 3 and RCL 4.

Code:

01  STO 0
02  x<>y
03  STO 2
04  1
05  STO 1
06  STO 3
07  STO 4
08  RCL 0
09  x=0?
10  GTO 21
11  RCL 2
12  STO×3
13  STO×4
14  RCL 1
15  STO÷4
16  1
17  STO-0
18  STO+1
19  STO-2
20  GTO 08
21  RCL 3
22  RCL 4
23  GTO 00

Edit: corrected an error several months after posting. #-)

25 [ENTER] 7 [R/S] => 480700   [x<>y] => 2422728000

This program should (usually) return accurate results if the latter can be respresented exactly with 10 digits.

Second, here is a deluxe version that calculates nCr and nPr. A negative r yields nPr, a positive r gives nCr:

25 [ENTER]  7 [R/S] => 480700
25 [ENTER] -7 [R/S] => 2422728000

Code:

01  ENTER
02  EEX
03  3
04  CHS
05  STO 3
06  CLX
07  x≤y?
08  GTO 19
09  +
10  x<>y
11  +
12  LstX
13  x≤y?
14  GTO 43
15  STO×3
16  1
17  -
18  GTO 13
19  +
20  x<>y
21  STO 2
22  x<>y
23  -
24  LstX
25  x≤y?
26  x<>y
27  x<>y
28  STO 0
29  1
30  STO 1
31  RCL 0
32  x=0?
33  GTO 43
34  RCL 2
35  STO×3
36  RCL 1
37  STO÷3
38  1
39  STO-0
40  STO+1
41  STO-2
42  GTO 31
43  EEX
44  3
45  STO×3
46  RCL 3
47  GTO 00

Ths program uses a trick (as proposed in the other thread I linked to earlier) to calculate nCr without overflow as long as the result does not exceed 9,999999999 E+99. Of course this also applies to nPr. There is no overflow unless the result overflows.

Both programs will correctly return 60 P 5 = 655381440. This is because they do not work with factorials but with repeated multiplication. Just as probably all (or at least most) calculators do in their internal nPr and nCr functions.

Of course this method is slower than calculating with factorials. But on a 12CP, let alone an emulator, this should not be an issue.

Dieter

[Gamo]

I just figure this out about result of Permutation or Combination that sometime return with decimal answer. Just by using FIX 0 and that should solve the problem.

Gamo.

[Dieter]

(08-24-2017 07:58 AM)Gamo Wrote:  I just figure this out about result of Permutation or Combination that sometime return with decimal answer. Just by using FIX 0 and that should solve the problem.

That's the same as rounding to the next integer. There is no guarantee that the result then is fine as the error can exceed 0,5.

Gamo, you really need to understand the math behind all this: why these roundoff errors happen and what can be done about it. Please, carefully read again the previous posts in this thread. And use one of the programs I posted yesterday.

Dieter

[Gamo]

Hello Dieter

deluxe version fix the problem

Gamo

[Dieter]

(08-24-2017 08:11 AM)Gamo Wrote:  deluxe version fix the problem

The compact version does so either.

Re. your suggestion of setting the display to FIX 0, i.e. rounding the result to the nearest integer: as already mentioned, this does not guarantee a correct result as the error may be as large as one unit in the 9th digit. But if factorials are used the domain for n and r is limited to 0...69 so there there is only a limited number of possible combinations. A test with n=1...69 and r=1...n showed that the worst case is P(64, 5) which is returned as 914941440,4 when calculated with factorials. So rounding to the nearest integer may actually work ...for results < 1E+9.

However, there may be errors in the last digit where rounding to the nearest integer does not work as the result already is a 10-digit integer. Take the example P(25, 7). It is returned as 25!/18! = 2422727999. The same is true for P(29, 7), for P(41, 6) etc. etc. Rounding to the nearest integer will not change anything as the result already is an integer. #-)

If you do the rounding by means of the usual procedure "0,5 + INTG" this will increase a 10-digit integer by 1 (thus returning a correct result for P(25, 7)), but already accurate 10-digit results will be increased as well, which again leads to an error. Results which are 1 unit high will even increase their error. For instance P(42, 6) yields 42!/36! = 3776965921 instead of ...920. Numerical rounding would change this to ...922. Or P(45, 6) is calculated as 45!/39! = 5864443202 which is even 2 ULP high. So rounding, either by setting FIX 0 or numerically, does not fix the problem.

Use one of the recent two programs and at least up to 1E+10 the results should be fine. ;-)

Dieter

[Gamo]

Hello Dieter

Both program is much refine they both work very well just like the result that on the build-in functions like you said most calculator must be using this formula. The formula you use I still need to look over and study in more detail and the programing style too.

Thank You

Gamo

[Gamo]

Permutation Manual Calculation yield different answer.

25P7

Manual Calculation steps:

1. 25 ENTER 7 - [n!] 25 [n!] / [1/x] result 2,422,728,000

2. 25 [n!] [LSTx] 7 - [n!] / --------- result 2,422,727,999

HP 12C Platinum gave same result either ways

Gamo