The following MIPS code computes the fibonacci sequence for a number, recursivel
ID: 3670993 • Letter: T
Question
The following MIPS code computes the fibonacci sequence for a number, recursively. What is the total number of MIPS instructions required to execute the function for n=10?
Here is the MIPS code:
.text
.globl fib
fib:
addi $sp, $sp, -12
sw $ra, 8($sp)
sw $a0, 4($sp)
sw $s1, 0($sp)
slti $t0, $a0, 2
beq $t0, $zero, Here
add $v0, $a0, $zero
addi $sp, $sp, 12
jr $ra
Here:
addi $a0, $a0, -1
jal fib
add $s1, $zero, $v0
addi $a0, $a0, -2
jal fib
add $v0, $v0, $s1
lw $s1, 0($sp)
lw $ra, 8($sp)
addi $sp, $sp, 12
jr $ra
and here is the corresponding test file to run it:
.text
.globl main
main:
addu $s7, $ra, $zero, # Save the ra
la $a0, int_prompt # Display the prompt
li $v0, 4
syscall
li $v0, 5 # Read an integer from the user
syscall
bgtz $v0, positive # If the number is not positive,
# we negate the number.
sub $v0, $zero, $v0
positive:
slti $s1, $v0, 1001 # is $v0 <= 1000
bne $s1, $zero, within_limit
li $v0, 1000
within_limit:
add $s2, $v0, $zero #save the value to s2 for later use
add $a0, $v0, $zero #save the value to a0
jal fib
add $s1, $v0, $zero # We save the result first
la $a0, fib_msg
li $v0, 4
syscall
add $a0, $s1, $zero # $a0 is the integer to be printed
li $v0, 1 # system call to print an integer
syscall # print int
la $a0, newline
li $v0, 4
syscall
la $t1, array_fib # $t1 is the address of the array we save to
add $s3, $zero, $zero
sw $s3, 0($t1)
addi $s4, $zero, 1
sw $s4, 4($t1)
add $s5, $zero, $zero
fib_loop:
slti $s6, $s5, 501
beq $s6, $zero, fib_loop_done
addiu $t1, $t1, 8
addu $s3, $s3, $s4
sw $s3, 0($t1)
addu $s4, $s3, $s4
sw $s4, 4($t1)
addi $s5, $s5, 1
j fib_loop
fib_loop_done:
la $s4, array_fib
sll $s2, $s2, 2
add $s4, $s4, $s2
lw $s4, 0($s4)
beq $s4, $s1, Correct
la $a0, wrong_message
j End_output
Correct:
la $a0, correct_message
End_output:
li $v0, 4
syscall
la $a0, newline
li $v0, 4
syscall
addu $ra, $zero, $s7 #restore $ra since the function calles
#another function
jr $ra
add $zero, $zero, $zero
add $zero, $zero, $zero
########## End of main function #########
.data
#Data segment starts here
fib_msg:
.asciiz "The result from your fib function is "
newline:
.asciiz ". "
int_prompt:
.asciiz "Please enter an integer (between 0 and 1000, overflow happens when larger than 46): "
wrong_message:
.asciiz "Your result is incorrect"
correct_message:
.asciiz "Your result is correct"
array_fib:
.align 2
.space 4096
Explanation / Answer
One implementation of the fib function:
# The corresponding C code might look like this:
#
# int fib(int N) {
# if (N == 0) return 0;
# if (N == 1) return 1;
# return fib(N-1) + fib(N-2);
# }
# input: N in $s0
# output: fib(N) in $s0
.text
.globl __start
__start:
or $a0, $zero, $s0 # Call fib(N)
jal fib
or $zero, $zero, $zero # nop in delay slot
or $s0, $zero, $v0 # Save the returned value of fib(N)
# Exit
addiu $v0, $zero, 10 # Prepare to exit (system call 10)
syscall # Exit
# Fib takes a single argument N in $a0, and returns fib(N) in $v0
# Uses registers as follows:
# s0 - saved N (preserved across calls)
# s1 - fib(N-1)
# s2 - fib(N-2)
fib:
# Save return address
addi $sp, $sp, -4
sw $ra, 0($sp)
# fib(0) case (return 0)
or $v0, $zero, $zero
beq $a0, $zero, end
or $zero, $zero, $zero # nop in delay slot
# fib(1) case (return 1)
ori $v0, $zero, 1
beq $a0, $v0, end
or $zero, $zero, $zero # nop in delay slot
# Recursion
# Save s0
addi $sp, $sp, -8
sw $s0, 0($sp)
sw $s1, 4($sp)
# Recover N from a0
or $s0, $zero, $a0
# Get fib(N-1)
addi $a0, $s0, -1 # N-1
jal fib
or $zero, $zero, $zero # nop in delay slot
or $s1, $v0, $zero # Save fib(N-1)
# Get fib(N-2)
addi $a0, $s0, -2 # N-2
jal fib
or $zero, $zero, $zero # nop in delay slot
or $s2, $v0, $zero # Save fib(N-2)
# Return fib(N-1) + fib(N-2)
add $v0, $s1, $s2
# Restore s0, s1, s2
lw $s0, 0($sp)
lw $s1, 4($sp)
addi $sp, $sp, 8
end:
lw $ra, 0($sp)
addi $sp, $sp, 4 # Note: Fills load delay
jr $ra
or $zero, $zero, $zero # nop in delay slot