MIPS Assembly MARS Program to Implement Recursion Assignment Solution

Instructions

Objective

Write an assembly language assignment program to implement recursion in a program.

Requirements and Specifications

Below is a variation of a Fibonacci sequence, not an original. Many such variations exist.

Implement the below function using the MARS Mips assembler. Call the function repeatedly to produce the output as shown below. For your convenience you are given the function in symbolic and C code.

ZIBO NACCI

This is a weird rendition of Fibonacci which tends to calculate results which appear to zig and zag.

• zib(0) = 1
• zib(1) = 1
• zib(2) = 2
• zib(2n+1) = zib(n) + zib(n-1) + 1, if n>0 (odd values 3 and higher)
• zib(2n) = zib(n) + zib(n+1) + 1, if n>1 (even values 4 and higher)

The C program to calculate this looks like:

Part B

Written portion: Using your student number which will appear in the following format, abcDEFG. This will produce the two base 10 numbers, D.E x 102, and F.G x 103. Take your student number and substitute in the digits as shown above. Using the FPS website (see course home page) convert each over to a normalized binary form. Each should look something like 1.xxxxxxxx * 2y. Depending on your student number, the number of significant digits will vary.

For those students who have DE and/or FG equal to zero, i.e. 0.0x102, then substitute 34 for any occurrence of 00 to ensure a non-zero term.

Using the FPS multiplication shown in class, multiply the above numbers together, producing a FPS result. Show all work, that is where the marks are. You can verify your work by doing a base 10 multiplication and using the FPS website to verify the binary result.

Screenshots of output

Source Code

.data RECORDS: .space 1024 S: .text main: la $s7, S # load address of end of records in s7 li $s0, 1 # first number to calculate loop: move $a0, $s0 # pass number to subroutine jal zib # zib(i) # print number move $a0, $v0 # move return value to a0 to print it li $v0, 1 # syscall number to print integer syscall # print space li $a0, 32 # load ascii space value li $v0, 11 # syscall number to print character syscall addi $s0, $s0, 1 # increment number to calculate ble $s0, 20, loop # repeat while number is below or equal to 20 # exit program li $v0,10 # syscall number to exit program syscall #------------------------------------------------------------------------------- # zib recursive subroutine, requires the number in a0, returns the result in v0 #------------------------------------------------------------------------------- zib: # create new record in s7 addi $s7, $s7, -12 # allocate space to save 3 registers sw $ra, 0($s7) # save ra in record sw $s0, 4($s7) # save s0 in record sw $s1, 8($s7) # save s1 in record bne $a0, $zero, else1 # if (n == 0) li $v0, 1 # return 1; j return else1: bne $a0, 1, else2 # else if (n == 1) li $v0, 1 # return 1; j return else2: bne $a0, 2, else3 # else if (n == 2) li $v0, 2 # return 2; j return else3: andi $t0, $a0, 1 # else if (n%2 == 1 && n >= 3) // odd beq $t0, $zero, else4 # return zib((n-1)/2) + zib((n-1)/2-1) + 1; addi $a0, $a0, -1 # n-1 srl $a0, $a0, 1 # (n-1)/2 move $s0, $a0 jal zib # zib((n-1)/2) move $s1, $v0 # save result in s1 addi $a0, $s0, -1 # (n-1)/2 -1 jal zib # zib((n-1)/2-1) add $v0, $v0, $s1 # zib((n-1)/2) + zib((n-1)/2-1) addi $v0, $v0, 1 # zib((n-1)/2) + zib((n-1)/2-1) + 1 j return else4: # else if (n%2 == 0 && n >= 4) // even # return zib(n/2) + zib(n/2+1) + 1; srl $a0, $a0, 1 # n/2 move $s0, $a0 jal zib # zib(n/2) move $s1, $v0 # save result in s1 addi $a0, $s0, 1 # n/2 +1 jal zib # zib(n/2+1) add $v0, $v0, $s1 # zib(n/2) + zib(n/2+1) addi $v0, $v0, 1 # zib(n/2) + zib(n/2+1) + 1 return: # load old values from record and remove it lw $ra, 0($s7) # load ra from record lw $s0, 4($s7) # load s0 from record lw $s1, 8($s7) # load s1 from record addi $s7, $s7, 12 # remove space allocated for the record jr $ra # return to caller