HP Forums
Improved 19C/29C Factorial, Permutation & Combination - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: Improved 19C/29C Factorial, Permutation & Combination (/thread-14141.html)

Improved 19C/29C Factorial, Permutation & Combination - David Hayden - 12-09-2019 08:59 PM

Page 112 of the HP 19C/29C Applications Book (available on the museum thumb drive) contains programs to compute factorials, permutations and combinations. The instructions note that the programs don't handle values of n < 2.

In addition, the program for combinations contains a bug. When computing COMB(N,K), if K>N, the program attempts to jump to LBL 8 at step 45 to display "Error," but instead jumps to LBL 8 at step 82 and returns whatever happened to be in register R2.

This version handles n >= 0 and fixes the COMB bug. It is also shorter (65 steps vs. 84).

The COMB function handles large n and small k by alternately multiplying by one value and dividing by another. This also improves accuracy. It could be improved further using some of the techniques in this excellent thread:
https://www.hpmuseum.org/forum/archive/index.php?thread-3962.html

Edit: See also this version which is much smaller at the expense of handling a smaller range of values in COMB(n,k): https://www.hpmuseum.org/forum/thread-14358.html
USAGE:

To compute N!: Enter N and press GSB 1. Example: 5 GSB 1 yields 120

To compute PERM(N,K) (the number of ways to permute N items taken K at a time): Enter N, enter K, press GSB 2. Example: 5 ENTER 2 GSB 2 yields 20.

To compute COMB(N,K) (the number of ways to combine N items taken K at a time where order doesn't matter): Enter N, enter K, press GSB 3. Example 5 ENTER 2 GSB 3 yields 10.


Code:
01. g LBL 1         / 15 13 01        Compute X!
02. g X=0?          /    51 71
03. 1               /       01
04. STO 0           /    23 00
05. 1               /       01
06. g LBL 4         / 15 13 04
07. RCL 0           /    24 00
08. x               /       61
09. g DSZ           /    15 23
10. GTO 4           /    13 04
11. g RTN           /    15 12
12. g LBL 2         / 15 13 02        Permute Y items taken X at a time
13. f X>Y           /    14 51
14. GTO 8           /    13 08        error
15. g X=0?          /    51 71
16. GTO 7           /    13 07        Special case for P(Y,0) = 1
17. STO 0           /    23 00
18. x<->y           /       21
19. STO 1           /    23 01
20. GTO 6           /    13 06        Needed for P(Y,1)
21. g LBL 5         / 15 13 05        Compute products
22. RCL 1           /    24 01
23. RCL 0           /    24 00
24. -               /       41
25. x               /       61
26. g LBL 6         / 15 13 06
27. g DSZ           /    15 23
28. GTO 5           /    13 05
29. g RTN           /    15 12
30. g LBL 7         / 15 13 07        
31. 1               /       01
32. g RTN           /    15 12
33. g LBL 8         / 15 13 08        Divide by zero to display "Error"
34. 0               /       00
35. /               /       71
36. g LBL 3         / 15 13 03        Comb(Y,X): Y items taken X at a time
37. f X>Y           /    14 51
38. GTO 8           /    13 08        Error
39. -               /       41
40. f LastX         /    14 73
41. f X<=Y          /    14 41        Get the smaller of X, Y-X
42. x<->y           /       21
43. STO 0           /    23 00        R0 = numerator
44. STO 1           /    23 01        R1 = numerator - denominator
45. +               /       51
46. STO 2           /    23 02        R2 = Y
47. 1               /       01
48. GTO 6           /    13 06
49. g LBL 0         / 15 13 00
50. x<->y           /       21
51. ROLDN           /       22
52. x               /       61        Multiply my current numerator
53. f LastX         /    14 73
54. RCL 1           /    24 01
55. -               /       41
56. /               /       71        Divide by numerator - delta
57. g LBL 6         / 15 13 06
58. g ISZ           /    15 24        Increment numerator. Never jumps
59. RCL 2           /    24 02
60. RCL 0           /    24 00
61. f X<=Y          /    14 41        Check for end of loop
62. GTO 0           /    13 00
63. ROLDN           /       22        Recover product and return
64. ROLDN           /       22
65. g RTN           /    15 12