Assignment Instructions: 1) The Factorial The factorial of a non-negative intege

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:

#####################################################################################

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

#####################################################################################

.data

.align 2

prompt:   .asciiz " Give me a value for "N" : "

msg: .asciiz " N factorial is: "

bye: .asciiz " *** 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

Explanation / Answer

# 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 " "

.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

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.