combination_example.hmmm

################################################################################
# Combinations C(n,k) solution
# C(n,k) = n! / (k! * (n-k)!)
# JAMES WARD
################################################################################

################################################################################
# register usage
################################################################################
# r0  <- 0
# r1  <- Function argument / calculations
# r2  <- n (preserved)
# r3  <- k (preserved)
# r4  <- n! result
# r5  <- k! result  
# r6  <- (n-k)! result
# r7  <- Temporary calculations
# r13 <- Function return value
# r14 <- Function return address
# r15 <- Stack pointer

################################################################################
# AREA: GET USER INPUT AND VALIDATE
################################################################################
0       read    r2              # Save n from input
1       read    r3              # Save k from input

# Check if n <= 0 or k <= 0
2       jeqzn   r2, 33          # If n == 0, return -1
3       jltzn   r2, 33          # If n < 0, return -1
4       jeqzn   r3, 33          # If k == 0, return -1
5       jltzn   r3, 33          # If k < 0, return -1

################################################################################
# AREA: PREPARE FUNCTION CALLS AND CALCULATE FACTORIALS
################################################################################
6       setn    r15, 60         # Initialize stack pointer

# Calculate n!
7       copy    r1, r2          # Set argument for factorial (n)
8       calln   r14, 21         # Call factorial(n)
9       copy    r4, r13         # Save n! result

# Calculate k!
10      copy    r1, r3          # Set argument for factorial (k)
11      calln   r14, 21         # Call factorial(k)
12      copy    r5, r13         # Save k! result

# Calculate (n-k)!
13      copy    r1, r2          # Restore original n
14      sub     r1, r1, r3      # Compute n-k
15      calln   r14, 21         # Call factorial(n-k)
16      copy    r6, r13         # Save (n-k)! result

################################################################################
# AREA: FINAL CALCULATIONS FOR C(n,k)
################################################################################
# Compute combinations formula: C(n,k) = n! / (k! * (n-k)!)
17      mul     r7, r5, r6      # Compute denominator: k! * (n-k)!
18      div     r1, r4, r7      # Compute final result: n! / denominator
19      write   r1              # Output the final result
20      halt                    # End program

################################################################################
# AREA: FACTORIAL FUNCTION - factorial(x)
################################################################################
# Before function begins: save return address and set up stack frame
21      pushr   r14, r15        # Save return address to stack

# Base case: if x == 0, return 1
22      jeqzn   r1, 30          # If x == 0, jump to base case handler

# Recursive case: factorial(x) = x * factorial(x-1)
23      pushr   r1, r15         # Save current x to stack
24      addn    r1, -1          # Compute x-1 for recursive call
25      calln   r14, 21         # Recursive call TEST!!!
26      popr    r1, r15         # Restore original x value from stack
27      mul     r13, r13, r1    # Compute x * factorial(x-1)

# After function ends: restore return address and return
28      popr    r14, r15        # Restore return address from stack
29      jumpr   r14             # Return to caller

# Base case handler: 0! = 1
30      setn    r13, 1          # Base case: return 1
31      popr    r14, r15        # Restore return address from stack
32      jumpr   r14             # Return to caller

################################################################################
# AREA: HANDLE INPUT VALUES <= 0
################################################################################
# Handle invalid input (n <= 0 or k <= 0) by returning -1
33      setn    r1, -1          # Load error code -1
34      write   r1              # Output error code
35      halt                    # End program