Routine in MIPS Running On Qtspim That Calculates Fibonacci Value Using a Recursion Assignment Solution

Instructions

Objective

Write an assembly language assignment 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