In: Electrical Engineering
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:
#####################################################################################
# Functional Description: Main program to test Factorial function # Enter a negative number to terminate run
#####################################################################################
.data
.align 2
prompt: .asciiz "\n\n Give me a value for \"N\" : "
msg: .asciiz " N factorial is: "
bye: .asciiz " \n *** Good-Bye ***"
.text
main: addiu $sp, $sp, -8 #Allocate space
mloop:
li $v0, 4
la $a0, prompt
syscall
li $v0, 5 #Get value for N
syscall
bltz $v0, quit
sw $v0, 0 ($sp)
jal Fac # Call factorial
li $v0, 4 # Print message
la $a0, msg
syscall
lw $a0, 4($sp) #Get result
li $v0, 1
syscall #Print factorial
b mloop
quit:
addiu $sp, 8 # Deallocate space
li $v0, 4 la $a0, bye
syscall li $v0, 10
syscall
#####################################################################################
# Functional Description: Recursive Factorial Fac (N: in, N! :out)
#####################################################################################
Fac:
lw $a0, 0 ($sp)
bltz $a0, Problem
addi $t1, $a0, -13
bgtz $t1, Problem # 13 is largest value we can
# accept
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
Problem:
sw $0, 4 ($sp)
jr $ra
Second give code file:
#####################################################################################
# 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
eqz $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
# Start of Program
The Factorial and Recursive definition of the multiplication
.data
msg_str: .asciiz "Enter any 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
#We can 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
# We can 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)
#PERFORM 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