(12C) Combination and Permutation
08-17-2017, 09:49 PM (This post was last modified: 08-17-2017 10:05 PM by BartDB.)
Post: #1
 BartDB Member Posts: 105 Joined: Feb 2015
(12C) Combination and Permutation
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  ; end

Accuracies (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}
08-18-2017, 08:28 AM
Post: #2
 Gamo Member Posts: 245 Joined: Dec 2016
RE: (12C) Combination and Permutation
Hello BartDB

Your program is very good, keep the good work !!

Gamo
08-18-2017, 08:55 AM (This post was last modified: 08-18-2017 08:56 AM by pier4r.)
Post: #3
 pier4r Senior Member Posts: 1,534 Joined: Nov 2014
RE: (12C) Combination and Permutation
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}

Wikis are great, Contribute :)
08-18-2017, 11:36 AM (This post was last modified: 08-18-2017 11:36 AM by Gamo.)
Post: #4
 Gamo Member Posts: 245 Joined: Dec 2016
RE: (12C) Combination and Permutation
HP Prime on CAS mode

5000 P 27 result
69446224525439268794572102670318704884478498898385274145791051328237007711099346​99558993920000000000 same result from WolfarmAlpha.

HP Prime calculate just like a real computer computation this is a very capable calculator ever!!!

Gamo
08-18-2017, 12:50 PM
Post: #5
 pier4r Senior Member Posts: 1,534 Joined: Nov 2014
RE: (12C) Combination and Permutation
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).

Wikis are great, Contribute :)
08-18-2017, 02:54 PM (This post was last modified: 08-18-2017 02:56 PM by Joe Horn.)
Post: #6
 Joe Horn Senior Member Posts: 1,232 Joined: Dec 2013
RE: (12C) Combination and Permutation
(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.

X<> c
-Joe-
08-18-2017, 03:18 PM
Post: #7
 pier4r Senior Member Posts: 1,534 Joined: Nov 2014
RE: (12C) Combination and Permutation
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.

Wikis are great, Contribute :)
08-18-2017, 04:58 PM
Post: #8
 BartDB Member Posts: 105 Joined: Feb 2015
RE: (12C) Combination and Permutation
(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:
08-18-2017, 05:12 PM (This post was last modified: 08-18-2017 05:13 PM by pier4r.)
Post: #9
 pier4r Senior Member Posts: 1,534 Joined: Nov 2014
RE: (12C) Combination and Permutation
(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:

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.

Wikis are great, Contribute :)
08-19-2017, 05:26 PM (This post was last modified: 08-19-2017 06:00 PM by Dieter.)
Post: #10
 Dieter Senior Member Posts: 2,021 Joined: Dec 2013
RE: (12C) Combination and Permutation
(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 32

Dieter
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)