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).

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay