+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (12C) Combination and Permutation (/thread-8856.html)
(12C) Combination and Permutation - BartDB - 08-17-2017 09:49 PM
C(n,r) and P(n,r) for HP-12C.
This should work for all cases where the result is less than 1E100.
The C(n,r) routine is based on the identity C(n,r) = C(n,n-r), selecting the minimum value of r and n-r for the calculations. In the loop body, the division and multiplication are done alternately to avoid overflows in cases where the intermediate calculations exceed the dynamic range of the HP-12C. Since doing division can result in non-integer results, the final result is rounded to the nearest integer.
The P(n,r) routine is based on the identity P(n,r) = n x (n-1) x (n-2) x ... x (n-r+1).
To use the C(n,r) routine, position the program counter at step 0 if it's not there already, key in n, hit enter, key in r and hit R/S.
To use the P(n,r) routine, position the program counter at step 25 (GTO 25), key in n, hit enter, key in r and hit R/S.
Code:
01 - ; X=n-r
02 lastx ; X=r, Y=n-r
03 X<>y ; for X and Y comparison in next step
04 x<=y ; would like to use X>Y? test to save previous step, but not available on 12C
05 x<>y ; place minimum of r and n-r in X
06 + ; X=n
07 sto 1 ; Store n in R1
08 lastx ; X=min(r,n-r)
09 sto 0 ; store in R0. Use as loop counter
10 1 ; Initial value is 1
11 sto 3 ; R3 = result register
12 rcl 0 ; X = loop counter
13 x=0 ; have we reached the end?
14 gto 22 ; if so, then exit
15 sto/ 3 ; update the result
16 rcl 1 ; recall next numerator factor
17 sto* 3 ; update the result
18 1 ;
19 sto- 0 ; decrement loop count
20 sto- 1 ; decrement numerator factor
21 gto 12 ; loop
22 rcl 3 ; place the result on the stack
23 intg ; take integer
24 gto 00 ; end
25 x<>y ; P(n,r) routine. X=n, Y=r
26 sto 0 ; Store n in R0
27 x<>y ; X=r, Y=n
28 - ; X=n-r
29 rcl 0 ; X=n, y=n-r
30 1 ;
31 - ; subtract 1 from X
32 x<=y ; are we done yet?
33 gto 36 ; if so, then display the result
34 sto* 0 ; update result
35 gto 30 ; loop
36 rcl 0 ; display the result
37 gto 00 ; endAccuracies (wrong didgits are underlined)
Combinations
\begin{array}{|l|r|r|}\hline Inputs & HP-12C & Wolfram Alpha \\\hline
15C5 & 3003 & 3003 \\\hline
36C7 & 8347680 & 8347680 \\\hline
90C7 & 747137556\underline{7} & 7471375560 \\\hline
101C6 & 126733992\underline{1} & 1267339920 \\\hline
70C8 & 94403509\underline{38} & 9440350920 \\\hline
425C23 & 5.9872995\underline{10}E37 & 5.987299532821716... E37 \\\hline
200C55 & 7.7183408\underline{23}E49 & 7.718340811430957... E49 \\\hline
335C167 & 3.044358\underline{801}E99 & 3.044358793146979... E99 \\\hline
\end{array}
Permutations
\begin{array}{|l|r|r|}\hline 25P7 & 2422728000 & 2422728000 \\\hline
99P5 & 8582777280 & 8582777280 \\\hline
100P45 & 7.35060259\underline{4}E84 & 7.350602595423500... E84 \\\hline
5000P27 & 6.94462245\underline{9}E99 & 6.944622452543926... E99 \\\hline
\end{array}
RE: (12C) Combination and Permutation - Gamo - 08-18-2017 08:28 AM
Hello BartDB
Your program is very good, keep the good work !!
Gamo
RE: (12C) Combination and Permutation - pier4r - 08-18-2017 08:55 AM
Just giving another comparison (against the sharp el506w with built in functions)
Accuracies (wrong didgits are underlined)
Combinations
\begin{array}{|l|r|r|}\hline Inputs & HP-12C & \texttt{Sharp el506w} \\\hline
15C5 & 3003 & 3003 \\\hline
36C7 & 8347680 & 8347680 \\\hline
90C7 & 747137556\underline{7} & 7471375560 \\\hline
101C6 & 126733992\underline{1} & 1267339920 \\\hline
70C8 & 94403509\underline{38} & 9440350920 \\\hline
425C23 & 5.9872995\underline{10}E37 & 5.98729953\underline{3}E37 \\\hline
200C55 & 7.7183408\underline{23}E49 & \texttt{error} \\\hline
335C167 & 3.044358\underline{801}E99 & \texttt{error} \\\hline
\end{array}
Permutations
\begin{array}{|l|r|r|}\hline 25P7 & 2422728000 & 2422728000 \\\hline
99P5 & 8582777280 & 8582777280 \\\hline
100P45 & 7.35060259\underline{4}E84 & 7.350602595E84 \\\hline
5000P27 & 6.94462245\underline{9}E99 & 6.94462245\underline{3}E99 \\\hline
\end{array}
RE: (12C) Combination and Permutation - Gamo - 08-18-2017 11:36 AM
HP Prime on CAS mode
5000 P 27 result
6944622452543926879457210267031870488447849889838527414579105132823700771109934699558993920000000000 same result from WolfarmAlpha.
HP Prime calculate just like a real computer computation this is a very capable calculator ever!!!
Gamo
RE: (12C) Combination and Permutation - pier4r - 08-18-2017 12:50 PM
The hp 50g does the same (and I guess all the math environments with exact computations/big integers , as long as the memory is enough).
RE: (12C) Combination and Permutation - Joe Horn - 08-18-2017 02:54 PM
(08-18-2017 12:50 PM)pier4r Wrote: The hp 50g does the same (and I guess all the math environments with exact computations/big integers , as long as the memory is enough).
Actually, both the 50g and Prime have built-in limitations on large integers, in different ways.
The 50g doesn't allow integer exponents greater than 9999 (e.g. 2^9999 works but 2^10000 says "^ Error: Integer too large"). However, the 50g allows the integers themselves to be as big as available memory (as you said), e.g. 2^9999 can be squared without error, and squared again, and so on, until you run out of memory.
Prime however imposes a maximum size on large integers themselves, regardless of available memory. It seems to be 2^8599-1, but I've not seen that documented anywhere. Try this in CAS on your Prime: \[\left ( 2^{8598}-1 \right )\cdot 2+1\]This yields an integer that contains 2589 digits. But now try to add 1 to it, and it yields infinity. So I think that's Prime's largest allowed integer, approximately 3.6E2588.
RE: (12C) Combination and Permutation - pier4r - 08-18-2017 03:18 PM
Nice info there Joe! Many thanks for sharing!
impressive the 50g though, as I would have expected the prime to show off with all its memory.
RE: (12C) Combination and Permutation - BartDB - 08-18-2017 04:58 PM
(08-18-2017 08:55 AM)pier4r Wrote: Just giving another comparison (against the sharp el506w with built in functions)
Accuracies (wrong didgits are underlined)
Hi, I see there are a few error entries. You might be interested in this thread in the old forum:
http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/archv019.cgi?read=173300
RE: (12C) Combination and Permutation - pier4r - 08-18-2017 05:12 PM
(08-18-2017 04:58 PM)BartDB Wrote: Hi, I see there are a few error entries. You might be interested in this thread in the old forum:
http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/archv019.cgi?read=173300
Nice find! As users in the thread linked observed I have the 506W not the W506, still the creativity impresses me to abuse the integration function. This are the real calculator users! The ones that know the math/implementation well enough to bent the calculator in many cases to their needs, even when according to the manual there is no other way.
Let's see if I am able to reproduce the steps.
RE: (12C) Combination and Permutation - Dieter - 08-19-2017 05:26 PM
(08-17-2017 09:49 PM)BartDB Wrote: The C(n,r) routine is based on the identity C(n,r) = C(n,n-r), selecting the minimum value of r and n-r for the calculations.
That's a good idea that can significantly speed up the calculation. But your program chooses the maximum instead of the minimum. ;-) Swap steps 03 and 04 and the program should work as intended.
(08-17-2017 09:49 PM)BartDB Wrote: In the loop body, the division and multiplication are done alternately to avoid overflows in cases where the intermediate calculations exceed the dynamic range of the HP-12C. Since doing division can result in non-integer results, the final result is rounded to the nearest integer.
The result is not rounded but truncated. If you want to round you should add a small amount like 0,1 or 0,3 before INTG trims off the decimals.
But you can address the roundoff problem by counting the denominator up instead of down. This yields integer results after each division. On the other hand overflow may occur a little bit earlier, but this can be handled by initializing R3 with 0,001 instead of 1 and finally multiplying the result by 1000.
(08-17-2017 09:49 PM)BartDB Wrote: The P(n,r) routine is based on the identity P(n,r) = n x (n-1) x (n-2) x ... x (n-r+1).
That's a nice and very compact routine. But does it also return correct results for r=0 ?
Maybe this works better:
Code:
.. ...
25 CHS
26 x<>y
27 +
28 LstX
29 1
30 STO 3
31 R↓
32 x≤y?
33 GTO 22
34 STO*3
35 1
36 -
37 GTO 32Dieter
RE: (12C) Combination and Permutation - Gamo - 03-15-2020 11:37 AM
Combination and Permutation program for HP-12C
--------------------------------------------------------
For Combination assuming that user already know that
mCo = mCm = 1
mC1 = m
For Permutation assuming tha user already know that
mPo = 1
mP1 = m
mPm = m!
--------------------------------------------------------
Formula used:
C(m,n) = [m x (m-1) x (m-2) x ... x (m-n+1)] ÷ (1 x 2 x 3 x ... x n)
P(m,n) = m x (m-1) x (m-2) x ... x (m-n+1)
--------------------------------------------------------
Program:
Code:
01 ENTER
02 STO 0
03 R/S
04 STO 1
05 1
06 -
07 1
08 +
09 -
10 1
11 +
12 x
13 LSTx
14 RCL 0
15 1
16 -
17 X≤Y
18 GTO 21
19 R↓
20 GTO 10
21 R↓
22 R↓
23 ENTER
24 RCL 1
25 n!
26 ÷
27 GTO 00Remark: For 2 ≤ n
Example: [FIX] 0
80C5 and 80P5
80 [R/S] display 80
5 [R/S] display Combination 24,040,016
[X<>Y] display Permutation 2,884,801,920
-------------------------------------------------
Gamo 3/2020