Hi. I'm having trouble with a program I am writing in MIPS. This is an assignment, so I'll understand if no one helps. The program has two recursive functions: Power and Multiply. The basic algorithms for each are:
int Power(int base, int expon)
{
if(expon == 0)
return 1;
else return Multiply(base, Power(base, expon-1))
}
int Multiply(int multiplicand, int multiplier)
{
if(multiplier == 0 || multiplicand == 0)
return 0;
else if(multiplier > multiplicand)
return Multiply(multiplier, multiplicand)
else
return multiplicand + Multiply(multiplicand, multiplier-1)
}It seems very simple, but I just can't get it to work. Also, our algorithms may assume the base > 0, the exponent is not negative, and the result will fit in a word. My program is quite long, so here is what I have for just the Power and Multiply functions:
# Power
# Parameter: t8 = base
# Parameter: t9 = exponent
# t0 being used
# t1 being used
# Returned value in s7
.text
.ent Power
Power:
addi $sp,$sp,-4
sw $ra,0($sp)
li $v0,4 # "Power("
la $a0,power
syscall
li $v0,1 # output t8
move $a0,$t8
syscall
li $v0,4 # ","
la $a0,comma
syscall
li $v0,1 # output t9
move $a0,$t9
syscall
li $v0,4 # ")\n"
la $a0,cparen
syscall
beqz $t9,expIsZero # test if t9 = 0
expNotZero:
# PARAM: base. stayed same
addi $t9,$t9,-1 # PARAM: t9 = expon-1
jal Power # returned value in s7
move $t6,$t8 # PARAM: t6 = base
move $t7,$s7 # PARAM: t7 = Power(base,expon-1)
jal Multiply
j endPower
expIsZero:
li $s7,1 # if t9 = 0, return 1
endPower:
lw $ra,0($sp)
addi $sp,$sp,4
j $ra
.end
# Multiply
# Parameter: t6 = multiplicand
# Parameter: t7 = multiplier
# t0 being used
# t1 being used
# t2 temporary
# Returned value in s6
.text
.ent Multiply
Multiply:
addi $sp,$sp,-4 # allocate space on stack for $ra
sw $ra,0($sp) # save the return address on the stack
li $v0,4 # " "
la $a0,space
syscall
la $a0,multiply # "Multiply("
syscall
li $v0,1 # output t6
move $a0,$t6
syscall
li $v0,4 # ","
la $a0,comma
syscall
li $v0,1 # output t7
move $a0,$t7
syscall
li $v0,4 # ")\n"
la $a0,cparen
syscall
beqz $t7,IsZero # test if multiplier = 0
beqz $t6,IsZero # test if multiplicand = 0
elseIf:
bgt $t7,$t6,greater # test if multiplier > multiplicand
else:
# PARAM: multiplicand stays same
addi $t7,$t7,-1 # PARAM: multiplier = multiplier - 1
jal Multiply # returned value in s6
add $s6,$t6,$s6 # return multiplicand +
# Multiply(multiplicand,multiplier-1)
j endMultiply
greater:
move $t2,$t7 # swap the values and
move $t7,$t6 # call again
move $t6,$t2
jal Multiply
j endMultiply
IsZero:
li $s6,0 # return 0
endMultiply:
lw $ra,0($sp)
addi $sp,$sp,4
j $ra
.endThe output I am getting for Power(3,5) is:
Power(3,5)
Power(3,4)
Power(3,3)
Power(3,2)
Power(3,1)
Power(3,0)
Multiply(3,1)
Multiply(3,0)
Multiply(3,1)
Multiply(3,0)
Multiply(3,1)
Multiply(3,0)
Multiply(3,1)
Multiply(3,0)
Multiply(3,1)
Multiply(3,0)
1
...where 1 the final answer output in Main after Power finishes.
Everything is being called correctly, it just seems to be a logic problem. The program is due friday, so if anyone can lend some help, it would be greatly appreciated. I can post my entire code if needed, it just comes out lookin weird.
Thanks