Question

Assignment Instructions:

1) The Factorial

The factorial of a non-negative integer ??, denoted by ??!, is the product of all positive integers less than or equal to ??. The textbook has an example of a recursive MIPS implementation of factorial. Additionally, a simplified version of the MIPS assembly language recursive implementation of the factorial function is attached. Trace the factorial example carefully using QTSPIM

2) Recursive definition of multiplication

The function ??????????(??, ??) for two positive integers 1 ? ??, and 1 ? ??, is defined as the following:

??????????(??, 1) = ??; ??????????(??, ??) = ?? + ??????????(??, ?? ? 1)

Write a recursive version of ??????????() in C or C++ and a pseudo C program (based on chapter 2 in the book) then use these programs to develop a MIPS program that gets as input two integers 0 < ?? ? 255, and 0 < ?? ? 255, and returns the result of ??????????(??, ??) in $v1.

Your deliverable should be the pseudo C and the assembly level function

Given code file one:

//copyable code

1.

.data

messagestr: .asciiz "Enter Number: "

.text

.globl main

main:

la $a0, messagestr

#load the data

li $v0, 4

#system call

syscall

#load the data

li $v0, 5

#system call

syscall

#move the data

move $a0,$v0   

jal factorial

move $a0,$v0   

li $v0,1   

syscall

li $v0,10

syscall

factorial:

#add the value

addi $sp,$sp,-8

#store the value  

sw $s0,0($sp)

#store the value   

sw $ra,4($sp)

#move the data

move $s0,$a0

#load the data   

li $v0,0x00000001 # 1

beq $s0,$v0,loop2

#branch instruction  

addi $a0,$s0,-1   

jal factorial

#multiply the data

mult $v0,$s0   

mflo $v0   

j loop3

#loop

loop2:

li $v0,0x00000001

loop3:

lw $ra,4($sp)   

lw $s0,0($sp)   

addi $sp,$sp,8   

jr $ra # return

Given code file two:

#####################################################################################
#       Functional Description: Main program to test Factorial function
#       Enter a negative number to terminate run
#####################################################################################

                .data
                .align          2

                .text
main:           addiu           $sp,  $sp,  -8  # Allocate space
mloop:

                li              $v0,  4         # Get value for N

                sw              $v0, 0 ($sp)
                jal             Fac             # Call factorial
                or              $v1,  $v0, $0
                addiu           $sp,  8         # Deallocate space

                li              $v0,  10
                syscall
#####################################################################################
# Functional Description: Recursive Factorial Fac  (N:  in,  N! :out)
#####################################################################################
Fac:
        lw              $a0,   0 ($sp)


        addiu           $sp,   $sp,   -16       #   Allocate    
        sw              $ra,   12 ($sp)         #   Save return address
        sw              $a0,   8($sp)
        slti            $t0,   $a0,  2          #   If N is 1 or 0,  then return the value 1
        beqz            $t0,   Go
        li              $v0,   1
        b               facret
Go:
        addi            $a0,   $a0,   -1                #
        sw              $a0,   0 ($sp)          #   Pass N-1 to factorial function
        jal             Fac                     #   Recursive call
        lw              $v0,   4($sp)           #   Get  (N-1)  !  back.
        lw              $ra,  12  ($sp)
        lw              $a0,  8 ($sp)
        mult            $v0,  $a0                       #  N* (N-1)  !
        mflo            $v0
facret:
        addiu           $sp,  $sp,  16          #  Deallocate
        sw              $v0,  4 ($sp)
        jr              $ra

Answer 1

Answer:

Program

The Factorial & Recursive definition of multiplication

   .data
   msg_str:        .asciiz "Enter some Number: "
   .text
   .globl main
   main:
   la       $a0, msg_str
   li       $v0, 4
   syscall
   li       $v0, 5
   syscall
   move       $a0,$v0           # compute 4!
   jal       fac
   move   $a0,$v0           # get result
   li       $v0,1           # print integer
   syscall
   li       $v0,10
   syscall

   #
   # fac(arg) - computes factorial of arg (arg!)
   #   argument is passed in $a0
   # stack frame:
   #
   # | ...high address... |
   # |--------------------|
   # | |
   # |--------------------|
   # | return address | +4
   # |--------------------|
   # $sp->| saved $s0 | +0
   # |--------------------|
   # | ...low address... |
   #      
   #  
fac:
   # prologue to procedure
   addi $sp,$sp,-8       # push space for activation frame
   sw       $s0,0($sp)       # save $s0, which we use
   sw       $ra,4($sp)       # save return address
   # start of actual procedure work
   move $s0,$a0           # get argument ($a0)
   li       $v0,0x00000001   # 1
   beq       $s0,$v0,L2       # end of recursion?
   addi $a0,$s0,-1       # set up argument (f-1)
   jal       fac           # recursive call
   mult $v0,$s0           # multiply
   mflo $v0           # return mul result
   j       L3           # exit procedure via epilogue
L2:
   li       $v0,0x00000001 # return value
   # epilogue to exit procedure
L3:
   lw       $ra,4($sp)       # restore $ra
   lw       $s0,0($sp)       # restore $s0
   addi $sp,$sp,8       # pop activation frame
   jr       $ra               # return

b)
data
str1: .asciiz "Enter a: "
str2: .asciiz "Enter b: "
str5: .asciiz "a*b = "
newline: .asciiz "\n"
.text

main: li $v0, 4 # system call code for print_string
la $a0, str1 # address of str1
syscall # print str1

#get the first number from user, put it into $s0

li $v0, 5 # system call code for read_int
syscall # read an integer into $v0 from console
add $s0, $v0, $zero # copy $v0 into $s0 (a)

#read print_string for str2
li $v0, 4 # system call code for print_string
la $a0, str2 # address of str1
syscall # print str1

# get second number from user, put it into $t1
li $v0, 5 #load syscall for read_int
syscall #make the syscall
move $s1, $v0 #move the number read into $s1(b)

#DO THE CALCULATIONS................................................
div $s0, $s1 #diving $s0 by $s1
mflo $t0 #storing value of lo(quotient) in
#register $t0
mfhi $t1 #storing value of hi(remainder) in
#register $t1

mult $s0, $s1
mflo $t2

li $v0,1
move $a0, $t2
syscall

li $v0,4
la $a0, str5
syscall

#read print_string for str3
li $v0, 4 # system call code for print_string
la $a0, str3 # address of str1
syscall # print str1   

#print a/b
li $v0, 1 #load syscall print_int into $v0
move $a0, $t0 #move the number to print into $t2
syscall
# read print string for str4
li $v0, 4
la $a0, str4
syscall
# print remainder
li $v0, 1
move $a0, $t1
syscall

#end of program