+1 (315) 557-6473 

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

assembly language routine in MIPS running on QtSpim that calculates fibonacci value using recursion Mips assembly
assembly language routine in MIPS running on QtSpim that calculates fibonacci value using recursion Mips assembly 1
Screenshots of output
assembly language routine in MIPS running on QtSpim that calculates fibonacci value using recursion Mips assembly 2
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