Instructions
Objective
Write an assembly language routine in MIPS running on QtSpim that calculates fibonacci value using recursion.
Requirements and Specifications
Screenshots of output
Source Code
.data
#; System Service Codes
SYSTEM_EXIT = 10
SYSTEM_PRINT_INTEGER = 1
SYSTEM_PRINT_STRING = 4
SYSTEM_READ_INTEGER = 5
#; Input Parameters
MAXIMUM_FIBONACCI = 46
MINIMUM_FIBONACCI = 1
#; Strings
n: .word 0
answer: .word 0
newLine: .asciiz "\n"
errorRange: .asciiz "Number must be between 1 and 46.\n"
inputString: .asciiz "Calculate Fibonacci sequence number (1-46): "
resultString: .asciiz " function calls required."
resultTopDown: .asciiz "Top Down Fibonacci ("
resultBottomUp: .asciiz "Bottom Up Fibonacci ("
closeParenthese: .asciiz "): "
.text
.globl main
.ent main
main:
# Output the prompt message
li $v0, SYSTEM_PRINT_STRING
la $a0, inputString
syscall
# Reads input
li $v0, SYSTEM_READ_INTEGER
syscall
move $t1, $v0
checkRangeInput:
bltu $t1, MINIMUM_FIBONACCI, invalidRange
bgtu $t1, MAXIMUM_FIBONACCI, invalidRange
j validRange
invalidRange:
# Outputs error message for range input of Fibonacci number
li $v0, SYSTEM_PRINT_STRING
la $a0, errorRange
syscall
# Prints new line for formatting.
li $v0, SYSTEM_PRINT_STRING
la $a0, newLine
syscall
# Reprompt
li $v0, SYSTEM_PRINT_STRING
la $a0, inputString
syscall
# Reads input again.
li $v0, SYSTEM_READ_INTEGER
syscall
addi $t1, $v0, 0
j checkRangeInput
validRange:
move $s0, $t1
# Prints new line for formatting.
li $v0, SYSTEM_PRINT_STRING
la $a0, newLine # load address of string
syscall
# Call the function
move $a0, $s0 # copy number to argument
la $a1, n # load address of number of calls
li $t0, 1 # save 1 as initial number of calls
sw $t0, 0($a1)
jal recursiveFibonacci # calculate fib(number, &ncalls)
addu $s1, $zero, $v0 # save fib(n) result in s1
# print result message
li $v0, SYSTEM_PRINT_STRING
la $a0, resultTopDown
syscall
li $v0, SYSTEM_PRINT_INTEGER
move $a0, $s0 # load number n
syscall
li $v0, SYSTEM_PRINT_STRING
la $a0, closeParenthese # load address of string
syscall
li $v0, SYSTEM_PRINT_INTEGER
move $a0, $s1 # load top-down fib(n) result
syscall
# Prints new line for formatting.
li $v0, SYSTEM_PRINT_STRING
la $a0, newLine # load address of string
syscall
# print number of calls
li $v0, SYSTEM_PRINT_INTEGER
la $t0, n # load address of number of calls
lw $a0, 0($t0)
syscall
li $v0, SYSTEM_PRINT_STRING # syscall number to print a string
la $a0, resultString # load address of string
syscall
# Prints new line for formatting.
li $v0, SYSTEM_PRINT_STRING
la $a0, newLine # load address of string
syscall
# Prints new line for formatting.
li $v0, SYSTEM_PRINT_STRING
la $a0, newLine # load address of string
syscall
move $a0, $s0 # copy number to argument
li $a1, 1 # current value to calculate is 1
li $a2, 1 # set f(n-1) as 1
li $a3, 0 # set f(n-2) as zero
la $t0, n # load address of number of calls
li $t1, 1 # save 1 as initial number of calls
sw $t1, 0($t0)
addi $sp, $sp, -4 # push last argument
sw $t0, 0($sp)
jal loopedFibonacci # calculate fib(number, curn, f(n-1), f(n-2), &ncalls)
addi $sp, $sp, 4 # restore stack pointer
addu $s1, $zero, $v0 # save fib(n) result in s1
# print result message
li $v0, SYSTEM_PRINT_STRING
la $a0, resultBottomUp
syscall
li $v0, SYSTEM_PRINT_INTEGER
move $a0, $s0 # load number n
syscall
li $v0, SYSTEM_PRINT_STRING
la $a0, closeParenthese # load address of string
syscall
li $v0, SYSTEM_PRINT_INTEGER
move $a0, $s1 # load top-down fib(n) result
syscall
# Prints new line for formatting.
li $v0, SYSTEM_PRINT_STRING
la $a0, newLine # load address of string
syscall
# print number of calls
li $v0, SYSTEM_PRINT_INTEGER
la $t0, n # load address of number of calls
lw $a0, 0($t0)
syscall
li $v0, SYSTEM_PRINT_STRING # syscall number to print a string
la $a0, resultString # load address of string
syscall
# Prints new line for formatting.
li $v0, SYSTEM_PRINT_STRING
la $a0, newLine # load address of string
syscall
endProgram:
li $v0, SYSTEM_EXIT
syscall
.end main
#; This function will calculate the Fibonacci value by calling itself.
#; Two arguments will be used:
#; 1. The Value n to calculate as an integer.
#; 2. The number of function calls made by reference.
.globl recursiveFibonacci
.ent recursiveFibonacci
recursiveFibonacci:
addi $sp, $sp, -16 # allocate space for registers in stack
sw $ra, 0($sp) # save return address in stack
sw $s0, 4($sp) # save s0 in stack
sw $s1, 8($sp) # save s1 in stack
sw $s2,12($sp) # save s2 in stack
li $v0, 0
beq $a0, $v0, rfReturn # if n == 0, return 0
li $v0, 1
beq $a0, $v0, rfReturn # if n == 1, return 1
move $s0, $a0 # save n in s0
move $s1, $a1 # save address of ncalls in s1
addi $a0, $a0, -1 # calculate n-1
lw $t0, 0($a1)
addi $t0, $t0, 1 # pass number of calls +1
sw $t0, 0($a1)
jal recursiveFibonacci # fib(n-1)
move $s2, $v0 # save fib(n-1) in s2
addi $a0, $s0, -2 # calculate n-2
lw $t0, 0($s1)
addi $t0, $t0, 1 # pass number of calls + 1
sw $t0, 0($s1)
move $a1, $s1
jal recursiveFibonacci # fib(n-2)
add $v0, $v0, $s2 # return fib(n-1) + fib(n-2)
rfReturn:
lw $ra, 0($sp) # load return address
lw $s0, 4($sp) # load s0 from stack
lw $s1, 8($sp) # load s1 from stack
lw $s2,12($sp) # load s2 from stack
addi $sp, $sp, 16 # remove allocated space from stack
jr $ra
.end recursiveFibonacci
#; This function will mimic loop structure for a recursive function to find
#; the Fibonacci value.
#; Five arguments will be used:
#; 1. The final value n to calculate as an integer.
#; 2. The current value n to calculate as an integer.
#; 3. The value generated previously f(n-1) as an integer.
#; 4. The value generated previously f(n-2) as an integer.
#; 5. The number of function calls made by reference.
.globl loopedFibonacci
.ent loopedFibonacci
loopedFibonacci:
addi $sp, $sp, -8 # allocate space for registers
sw $ra, 0($sp) # save return address in stack
sw $fp, 4($sp) # save frame pointer in stack
move $fp, $sp # save frame pointer
li $v0, 0
beq $a1, $v0, skip # if curn == 0, skip
li $v0, 1
beq $a1, $v0, skip # if curn == 1, skip
add $v0, $a2, $a3 # f(n) = f(n-1)+f(n-2)
beq $a0, $a1, loopEnd # if n = curn, return value
move $a3, $a2 # use f(n-1) as f(n-2)
move $a2, $v0 # use current f as f(n-1)
skip:
addi $a1, $a1, 1 # increment current n being calculated
lw $t0, 8($fp) # load argument from stack
lw $t1, 0($t0)
addi $t1, $t1, 1 # pass number of calls +1
sw $t1, 0($t0)
addi $sp, $sp, -4 # push last argument (ncalls reference)
sw $t0, 0($sp)
jal loopedFibonacci # fib(n,curn+1,f(n-1),f(n-2), &ncalls))
addi $sp, $sp, 4 # restore stack pointer
loopEnd:
lw $ra, 0($sp) # load return address from stack
lw $fp, 4($sp) # load frame pointer from stack
addi $sp, $sp, 8 # remove allocated space from stack
jr $ra
.end loopedFibonacci