CODEWITHSUNDEEP
recursionmips
buncher
buncher

Reputation: 31

Recursion greatest common divisor in MIPS

In MIPS, I am trying to calculates the greatest common divisor (GCD) of pairs of positive integer numbers using the Euclidean algorithm. For example, the GCD of 6 and 9 is 3, while the GCD of 10 and 25 is 5.

The C code is something like this 

uint32_t m_w = 50000;
uint32_t m_z = 60000;
uint32_t hcf(uint32_t n1, uint32_t n2)
    {
        if (n2 != 0)
           return hcf(n2, n1%n2);
        else 
           return n1;
    }

And I am writing the MIPS program and I am not sure how to use n1 % n2. And this is my first time to do the recursion, and I am not sure the syntax is right or not 

.data
    n1: .word 6
    n2: .word 9

.text
.globl main
main:
    lw $a0,n1  # load value n1
    lw $a1,n2  #load value n2
    jal GCD # call funtion GCD

    add $a0,$v0,$zero 
    li $v0,1
    syscall # print result
li $v0, 10 # exit program 
syscall

GCD:
    #GCD(n1, n2)
    # n1 = $a0
    # n2 = $a1

    addi $sp, $sp, -12
    sw $ra, 0($sp) # save function into stack
    sw $s0, 4($sp) # save value $s0 into stack 
    sw $s1, 8($sp) # save value $s1 into stack 

    add $s0, $a0, $zero # s0 = a0 ( value n1 ) 
    add $s1, $a1, $zero # s1 = a1 ( value n2 ) 

    addi $t1, $zero, 0 # $t1 = 0
    beq $s1, $t1, returnn1 # if s1 == 0 returnn1

    addi $a0, $zero, $s1 # make a0 = $s1
    addi $a1, .... #  (n1%n2)
    jal GCD

exitGCD:
    lw $ra, 0 ($sp)  # read registers from stack
    lw $s0, 4 ($sp)
    lw $s1, 8 ($sp)
    addi $sp,$sp , 12 # bring back stack pointer
    jr $ra
returnn1:
    li $v0, $s0 # return $v0 = $s0 ( n1)
    j exitGCD

Upvotes: 2

Views: 5293

Answers (1)

can
can

Reputation: 444

You were almost there. Just like @Micheal said div and mfhi was all you needed. Modulo (% is modulo operator) is just reminder of a division between two integers. 

.data
n1: .word 60
n2: .word 45

.text
.globl main
main:
    lw $a0,n1  # load value n1
    lw $a1,n2  #load value n2
    jal GCD # call funtion GCD

    add $a0,$v0,$zero 
    li $v0,1
    syscall # print result
li $v0, 10 # exit program 
syscall

GCD:
    #GCD(n1, n2)
    # n1 = $a0
    # n2 = $a1

    addi $sp, $sp, -12
    sw $ra, 0($sp) # save function into stack
    sw $s0, 4($sp) # save value $s0 into stack 
    sw $s1, 8($sp) # save value $s1 into stack 

    add $s0, $a0, $zero # s0 = a0 ( value n1 ) 
    add $s1, $a1, $zero # s1 = a1 ( value n2 ) 

    addi $t1, $zero, 0 # $t1 = 0
    beq $s1, $t1, returnn1 # if s1 == 0 returnn1

    add $a0, $zero, $s1 # make a0 = $s1
    div $s0, $s1 # n1/n2
    mfhi $a1 # reminder of n1/n2 which is equal to n1%n2

    jal GCD

exitGCD:
    lw $ra, 0 ($sp)  # read registers from stack
    lw $s0, 4 ($sp)
    lw $s1, 8 ($sp)
    addi $sp,$sp , 12 # bring back stack pointer
    jr $ra
returnn1:
    add $v0, $zero, $s0 # return $v0 = $s0 ( n1)
    j exitGCD

Your code also had some syntax issues. You can read about div, mhfi in here

Upvotes: 3

Related Questions