Assignment Instructions 1 The Factorial The factorial of a n

Assignment Instructions:

1) The Factorial

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

2) Recursive definition of multiplication

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

rmult(a,1) = a;                rmult(a,b) = a + rmult(a,b-1)

Write a recurssive version of rmult() in C or C++ and a pseudo C program then use these programs to develop a MIPS program that gets as input two integers 0 < a 255, and 0 < b 255, and returns the result of rmult(a,b) in $v1.

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

Functional Description: Main program to test Factorial function

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

.data

.align   2

.text

main:

addiu $sp, $sp, -8 # Allocate space

mloop:

li $v0, 4 # get value of N

sw $v0, 0 ($sp)

jal Fac # Call factorial

or $v1, $v0, $0 #Result in $v1

addiu $sp, $sp, 8 # De-allocate 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, $ao, 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

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 # De-allocate

sw $v0, 4($sp)

jr $ra

Solution

1) Factorial program code was already given in question.

2) Recursive multiplication...

C CODE

int mult(a,b){
   if(b == 1){
       return a;
   }
   else if(b==0){
       return 0;
   }
   return a + mult(a,b-1);
}

-----------------------------------------------------------------------------------------------------------------------------------------

assembly code

   .file   \"c_he8jb4\"
   .text
   .p2align 2,,3
.globl _mult
   .def   _mult;   .scl   2;   .type   32;   .endef
_mult:
   pushl   %ebp
   movl   %esp, %ebp
   pushl   %ebx
   movl   8(%ebp), %eax
   movl   12(%ebp), %edx
   cmpl   $1, %edx
   je   L3
   testl   %edx, %edx
   je   L15
   movl   %eax, %ecx
   jmp   L7
   .p2align 2,,3
L8:
   addl   %eax, %ecx
   testl   %edx, %edx
   je   L16
L7:
   decl   %edx
   movl   %ecx, %ebx
   cmpl   $1, %edx
   jne   L8
   addl   %ecx, %eax
L3:
   popl   %ebx
   leave
   ret
L16:
   movl   %ebx, %eax
   popl   %ebx
   leave
   ret
L15:
   xorl   %eax, %eax
   jmp   L3

--------------------------------------------------------------------------------------------------------------------------------------------------------------

mips

.file   1 \"\"
   .section .mdebug.abi32
   .previous
   .gnu_attribute 4, 1
   .abicalls
   .text
   .align   2
   .globl   _Z4multii
$LFB0 = .
   .set   nomips16
   .ent   _Z4multii
   .type   _Z4multii, @function
_Z4multii:
   .frame   $sp,32,$31       # vars= 0, regs= 2/0, args= 16, gp= 8
   .mask   0x80010000,-4
   .fmask   0x00000000,0
   .set   noreorder
   .cpload   $25
   .set   nomacro
  
   addiu   $sp,$sp,-32
$LCFI0:
   sw   $31,28($sp)
$LCFI1:
   sw   $16,24($sp)
   movz   $31,$31,$0
$LCFI2:
   .cprestore   16
   li   $2,1           # 0x1
   beq   $5,$2,$L2
   move   $16,$4

   bne   $5,$0,$L3
   nop

   b   $L2
   move   $16,$0

$L3:
   lw   $25,%got(_Z4multii)($28)
   nop
   jalr   $25
   addiu   $5,$5,-1

   addu   $16,$16,$2
$L2:
   move   $2,$16
   lw   $31,28($sp)
   lw   $16,24($sp)
   j   $31
   addiu   $sp,$sp,32

   .set   macro
   .set   reorder
   .end   _Z4multii
$LFE0:
   .size   _Z4multii, .-_Z4multii
   .section   .eh_frame,\"aw\",@progbits
$Lframe1:
   .4byte   $LECIE1-$LSCIE1
$LSCIE1:
   .4byte   0x0
   .byte   0x1
   .globl   __gxx_personality_v0
   .ascii   \"zP\\000\"
   .uleb128 0x1
   .sleb128 -4
   .byte   0x1f
   .uleb128 0x5
   .byte   0x0
   .4byte   __gxx_personality_v0
   .byte   0xc
   .uleb128 0x1d
   .uleb128 0x0
   .align   2
$LECIE1:
$LSFDE1:
   .4byte   $LEFDE1-$LASFDE1
$LASFDE1:
   .4byte   $LASFDE1-$Lframe1
   .4byte   $LFB0
   .4byte   $LFE0-$LFB0
   .uleb128 0x0
   .byte   0x4
   .4byte   $LCFI0-$LFB0
   .byte   0xe
   .uleb128 0x20
   .byte   0x4
   .4byte   $LCFI2-$LCFI0
   .byte   0x11
   .uleb128 0x10
   .sleb128 2
   .byte   0x11
   .uleb128 0x1f
   .sleb128 1
   .align   2
$LEFDE1:
   .ident   \"GCC: (Debian 4.4.5-8) 4.4.5\"