DEV Community

Jack Lin
Jack Lin

Posted on • Edited on

5 2

Implement factorial using MIPS

This was a computer organization class assignment. I implemented a factorial using the following algorithm:

F(n)={1,n=0F(n1)n,nN F(n) = \begin{cases} 1, & n = 0 \\ F(n - 1) * n, & n \in \mathbb{N} \end{cases}

In MIPS, I use $a0 as the parameter n of F(n). For example, letting $a0 equal to 5 and jumping to the fact label means F(5), and at the end of the recursion, the result will be stored in $v0.

main:
    addi $a0, $zero, 5        # let the parameter n be 5
    jal fact                  # jump to fact label, i.e. calling F(5)
    j exit

fact:
    addi $sp, $sp, -8         # allocate 8 bytes to this stack
    sw $ra, 0($sp)            # save the address of the instruction that calls fact label (instruction address)
    sw $a0, 4($sp)            # save the value of n

    slti $t0, $a0, 1          # $t0 is used for conditions. If n < 1 then $t0 = 1, else $t0 = 0
    beq $t0, $zero, L1        # if $t0 == 0 then jump to branch L1
    addi $v0, $zero, 1        # let $v0 be 1
    addi $sp, $sp, 8          # let $sp point to upper stack
    jr $ra                    # jump to the next instruction of the instruction calling fact

L1:
    addi $a0, $a0, -1         # n = n - 1
    jal fact                  # jump to fact label again, like as calling F(n - 1)
    lw $a0, 4($sp)            # recover the value of n
    mul $v0, $a0, $v0         # $v0 *= $a0, like as F(n) = n * F(n - 1)
    lw $ra, 0($sp)            # recover instruction address
    addi, $sp, $sp, 8         # let $sp point to the upper stack
    jr $ra                    # jump to the next instruction of the instruction calling L1

exit:
Enter fullscreen mode Exit fullscreen mode

The execution result of the MARS simulator looks like this:

Image description

You can see that the value of $v0 is 0x78, 120 in decimal, which is the result of F(5).

Image of Datadog

How to Diagram Your Cloud Architecture

Cloud architecture diagrams provide critical visibility into the resources in your environment and how they’re connected. In our latest eBook, AWS Solution Architects Jason Mimick and James Wenzel walk through best practices on how to build effective and professional diagrams.

Download the Free eBook

Top comments (0)

Retry later
Retry later