MIPS中递归最大公约数 [英] Recursion greatest common divisor in MIPS

问题描述

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

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.

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.这是我第一次进行递归，而且我不确定语法是否正确

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

推荐答案

您快到了.就像@Micheal所说的div和mfhi是您所需要的.模数(％为模运算符)只是提醒两个整数之间的除法.

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

这篇关于MIPS中递归最大公约数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！