MIPS中的递归最大公约数

Question

在MIPS中，我尝试使用欧几里德算法计算成对的正整数的最大公约数(GCD)。例如，6和9的GCD是3，而10和25的GCD是5。

C代码是这样的

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;
    }

我正在编写MIPS程序，但我不确定如何使用n1 % n2。这是我第一次做递归，我不确定语法是否正确

.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

Answer 1

你就快到了。就像@Micheal说的那样，div和mfhi就是你所需要的。模(%是模运算符)只是两个整数之间的除法。

.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

您的代码还存在一些语法问题。您可以在here中阅读有关div、mhfi的内容。