Mips Calculate Factorial of N

Introduction

The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. The factorial of 0 is defined as 1. Factorials are widely used in combinatorics, probability, and algebra.

In MIPS assembly language, we can implement factorial calculation using either recursive or iterative approaches. Each method has its own advantages and considerations, which we'll explore in this guide.

How to Calculate Factorial in MIPS

There are two primary approaches to calculating factorials in MIPS: recursion and iteration. Let's examine each method.

Recursive Approach

The recursive approach leverages the mathematical definition of factorial:

In MIPS, we can implement this as:

factorial:
    # Save registers
    addi $sp, $sp, -8
    sw $ra, 4($sp)
    sw $s0, 0($sp)

    # Base case: if n == 0, return 1
    beq $a0, $zero, base_case

    # Recursive case: n! = n * (n-1)!
    move $s0, $a0
    addi $a0, $a0, -1
    jal factorial
    mul $v0, $s0, $v0

    # Restore registers and return
    lw $s0, 0($sp)
    lw $ra, 4($sp)
    addi $sp, $sp, 8
    jr $ra

base_case:
    li $v0, 1
    jr $ra

Iterative Approach

The iterative approach uses a loop to multiply numbers from 1 to n:

factorial:
    # Initialize result to 1
    li $v0, 1

    # If n == 0, return 1
    beq $a0, $zero, done

    # Multiply numbers from 1 to n
    li $t0, 1
loop:
    mul $v0, $v0, $t0
    addi $t0, $t0, 1
    ble $t0, $a0, loop

done:
    jr $ra

Example Calculation

Let's calculate 5! using both approaches.

Recursive Calculation

5! = 5 × 4! = 5 × (4 × 3!) = 5 × (4 × (3 × 2!)) = 5 × (4 × (3 × (2 × 1!))) = 5 × (4 × (3 × (2 × 1))) = 120

Iterative Calculation

1 × 2 × 3 × 4 × 5 = 120

MIPS Implementation

Here's a complete MIPS program that calculates factorials using both approaches:

# MIPS program to calculate factorial
.data
prompt: .asciiz "Enter a non-negative integer: "
result_msg: .asciiz "The factorial is: "

.text
main:
    # Print prompt
    li $v0, 4
    la $a0, prompt
    syscall

    # Read integer input
    li $v0, 5
    syscall
    move $a0, $v0

    # Call factorial function
    jal factorial

    # Print result message
    li $v0, 4
    la $a0, result_msg
    syscall

    # Print result
    li $v0, 1
    move $a0, $v0
    syscall

    # Exit program
    li $v0, 10
    syscall

# Recursive factorial function
factorial_recursive:
    # Save registers
    addi $sp, $sp, -8
    sw $ra, 4($sp)
    sw $s0, 0($sp)

    # Base case: if n == 0, return 1
    beq $a0, $zero, base_case_recursive

    # Recursive case: n! = n * (n-1)!
    move $s0, $a0
    addi $a0, $a0, -1
    jal factorial_recursive
    mul $v0, $s0, $v0

    # Restore registers and return
    lw $s0, 0($sp)
    lw $ra, 4($sp)
    addi $sp, $sp, 8
    jr $ra

base_case_recursive:
    li $v0, 1
    jr $ra

# Iterative factorial function
factorial_iterative:
    # Initialize result to 1
    li $v0, 1

    # If n == 0, return 1
    beq $a0, $zero, done_iterative

    # Multiply numbers from 1 to n
    li $t0, 1
loop_iterative:
    mul $v0, $v0, $t0
    addi $t0, $t0, 1
    ble $t0, $a0, loop_iterative

done_iterative:
    jr $ra