MIPS Assembly - Trying to write a recursive program to calculate nCr (Combination)

Question

I'm trying to create a mips assembly program to calculate nCr recursively.

I've written the whole program, including a driver, but It's not functioning correctly. All of my inputs and outputs work but my recursive algorithm is returning crazy numbers. For example, nCr ==268501120 instead of 10.

Updated code: http://pastebin.com/52ueQu99

Here's just a snippet of my algorithm:

nCk:
sub $sp, $sp, 16 #allocate the needed space in stack.
sw $ra, 0($sp) #save return address in first position
sw $t3, 4($sp) #save n in the stack
sw $t4, 8($sp) #save k in the stack

sub $t3, $t3, 1 #Subtract one from n
sub $t4, $t4, 1 #Subtract one from k

jal checkBounds #Check for end of recursion.
sw $v0, 12($sp) #copy returned 1 or 0 into stack.

lw $t3, 4($sp) #Load original n back into t3.
lw $t4, 8($sp) #Load original k back into t4.

sub $t3, $t3, 1 #Subtract one from n again. (n-1 step of recursive algorithm)
jal checkBounds #Check for end of recursion with n 1 number lower.

lw $t2, 12($sp) #Load the value held in the previously returned v0.
add $v0, $v0, $t2 #Add old returned value to new returned value.

lw $ra, 0($sp) #Load the original return address.
addi $sp, $sp, 16 #Add 16 more bytes to the stack.
jr $ra


checkBounds: #Check if program should still recurse
beq $t3, $t4, return1 #If n==k
beq $t4, $0, return1  #if k==0
li $v0, 0 #If (j!=k || k!=0){ return 0};
jal nCk
jr $ra 


return1: #Returns 1
li $v0, 1
jr $ra

Your `printAnswer` routine makes no sense to me. For example, the integer value you're printing at the end (which is supposed to be `n`) is actually the address of the `answerIs` string, unless I'm completely mistaken. — Michael, Dec 04 '13 at 17:32
You're more than likely right about that. I wasn't sure which param would hold the end result. I came to the conclusion that t3 held the result. I guess I was wrong? Do you have any idea how I can fix this? Thank you again for your help. — TJ Zimmerman, Dec 04 '13 at 17:46
It's quite possible that `$t3` holds `n` at that point - I didn't read all the code. But `$t3` isn't the argument for syscall 1; `$a0` is. So instead of that `la` instruction you probably want `move $a0,$t3`. The `la` pseudo-instruction is used for loading the address of something (typically a label) into a register. — Michael, Dec 04 '13 at 17:50
Haha, you're right! I wrote that instruction backwards. My program is working slightly better now. 5c2 returns -1 now instead of that huge number. — TJ Zimmerman, Dec 04 '13 at 17:57

score 2 · Answer 1 · answered Dec 04 '13 at 18:33

2

This code has so many errors it's hard to list. For starters, it has syntax errors and missing labels, so it doesn't even assemble. Then, the input values are never written into $t3 and $t4 because you got the operand order reversed. Furthermore, your CheckBounds uses JAL without saving $ra. Same goes for main. As for printing, the result is in $v0 so you need to save that before you clobber $v0 by printing the preceding stuff.

Fixing all those seems to make it work.

You should really learn to use a debugger/simulator to fix your bugs. For example, spotting that the registers don't have the expected values is easy.

answered Dec 04 '13 at 18:33

Jester

56,577
4
81
125

Thank you for your input. I appreciate your criticism. I only have about 2 weeks or ASM experience so I'm very knew to this. I'm using MARS to compile and it seems to work on my end. There aren't any syntax errors or missing labels? Mine compiles and runs I just get incorrect results. Thank you for your advice on instantiating t3 and t4. I often get confused about the mips instructions because it seems like some read forward and some backward. V0 is saved beginning at the 12th byte of my stack allocation? See line 82. I'm using the MARS debugger. It just makes my eyes bleed haha. – TJ Zimmerman Dec 04 '13 at 19:08
Line 22 is missing a `.asciiz` directive - syntax error. You don't have a `main` symbol defined. Beginning of `printAnswer` result is in `$v0` (due to line 91) but that's not saved and is subsequently destroyed by line 120. Thus, on line 136, `$t3` does not contain the result. – Jester Dec 04 '13 at 19:47
Ah, nice catch on the asciiz. Can't believe I overlooked that.. sorry. My class in globl and accessed by a test class provided by my professor. So it's called from the top. So I figured it would just flow from the .data straight down to the first line of code. Am I wrong to assume this? Thanks for the v0 destruction hint! – TJ Zimmerman Dec 04 '13 at 19:58
Updated code: http://pastebin.com/RN4Wba2y When I test it with manually passed params it always returns 2 and doesn't seem to recognize and invalid param. For example 5C2 should be 10 not 2. When I test it with my professor's test cases, it errors and says: Error in E:\Dropbox\School Stuff\College\Junior Year\Fall Semester\CIS 251\Assembly Homework 4\nCr.asm line 43: Runtime exception at 0x0040003c: invalid integer input (syscall 5) I have no idea what's going on now.. Any ideas? – TJ Zimmerman Dec 04 '13 at 20:55
1

You still don't have the initial `$t3`, `$t4` right (lines 35 and 45). Also, you tried to return value in `$v1` (line 92) but you haven't adjusted line 83 or 110 accordingly. Of course it'd be best to leave return value in `$v0` as usual, just save and restore it in the `printAnswer` appropriately. – Jester Dec 04 '13 at 22:58

score 1 · Accepted Answer · answered Dec 05 '13 at 07:38

I took the liberty of refactoring your code a little and skipping error checking part to show you the most important parts. Essentially I have implemented iterative factorial procedure that does not do any error checking on input value. Then in the main program I get inputs from the user, compute factorials and apply the formula. Hope that helps.

.data
    enterN: .asciiz "Please enter the n value: \n"
    enterK: .asciiz "Please enter the k value: \n"
    output: .asciiz "Result is: "
.text

j main

factorial:
    # iterative factorial procedure
    # $a0 - number, no error checking is performed on input
    # $v0 - factorial of the number
    addi $sp, $sp, -4
    sw $ra, 0($sp)

    li $v0, 1
    li $s0, 1
factorial_begin:
    beq $s0, $a0, factorial_end # n == 1?
    mul $v0, $v0, $a0 # $v0 = $v0 * n
    subi $a0, $a0, 1  # n = n - 1
    j factorial_begin
factorial_end:
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra


main:
    # compute cobination (n choose k) = n! / k!(n-k)!   
    # ----------------------------------------------
    la $a0, enterN #Ask for the first param, n.
    li $v0, 4 #String syscall
    syscall #Prints out string.
    li $v0, 5 
    syscall #Places inputted value in v0.
    la $t0, ($v0) # $t0 = n

    # computer factorial of n
    move $a0, $t0
    jal factorial
    move $t1, $v0 # $t1 = n!

    la $a0, enterK #Asks for the second param, k.
    li $v0, 4 #String syscall
    syscall #Prints out string
    li $v0, 5 
    syscall #Places inputted value in v0.
    la $t2, ($v0) # $t2 = k

    # computer factorial of k
    move $a0, $t2
    jal factorial
    move $t3, $v0 # $t3 = k!

    sub $a0, $t0, $t2 # $a0 = n - k
    jal factorial
    move $t4, $v0 # $t4 = (n-k)!

    mul $t3, $t3, $t4 # $t3 = k! * (n-k)!
    div $t1, $t1, $t3 # $t1 = n! / (k! * (n-k)!)

    # print out the result
    la $a0, output
    li $v0, 4
    syscall 

    move $a0, $t1
    li $v0, 1
    syscall

MIPS Assembly - Trying to write a recursive program to calculate nCr (Combination)

2 Answers2