0

我的任务是在 MIPS 汇编器中递归地实现埃及乘法。我想我理解了大部分相关内容，但我无法理解一件事：最终结果是如何计算的？例如在这段代码中（取自这个问题）：

# int fact(int n)
fact:
subu    sp, sp, 32  # Allocate a 32-byte stack frame
sw  ra, 20(sp)  # Save Return Address
sw  fp, 16(sp)  # Save old frame pointer
addiu   fp, sp, 28  # Setup new frame pointer
sw  a0,  0(fp)  # Save argument (n) to stack

lw  v0, 0(fp)   # Load n into v0
bgtz    v0, L2      # if n > 0 jump to rest of the function
li  v0, 1       # n==1, return 1
j   L1      # jump to frame clean-up code

L2:
lw  v1, 0(fp)   # Load n into v1
subu    v0, v1, 1   # Compute n-1
move    a0, v0      # Move n-1 into first argument
jal fact        # Recursive call

lw  v1, 0(fp)   # Load n into v1
mul v0, v0, v1  # Compute fact(n-1) * n

#Result is in v0, so clean up the stack and return
L1:
lw  ra, 20(sp)  # Restore return address
lw  fp, 16(sp)  # Restore frame pointer
addiu   sp, sp, 32  # Pop stack
jr  ra      # return
.end    fact

两条线之间的方式/时间

jal fact

和

L2

有没有达到？在我的理解中，要么 L1/L2 被分支到，要么事实被递归调用......

/编辑：

好的，看来我想出了如何在 MIPS 中递归地实现一些东西。但是，我还有最后一个问题：使用下面的代码，我的程序缺少一个“转”，这意味着在计算最终结果时不考虑最后一个值。

pharao:
    li $t0, 2       #load imm for division by 2
    lw $a0, fac_1       #load fac_1 into $a0
    lw $a1, fac_2       #load fac_2 into $a1
    li $t7, 0       #zero $t7
    li $t6, 1       #load 1 into $t6

    jal egypt       #jump to egypt
    j end




egypt:      
    subiu $sp,$sp,16    #space on stack for 4 values
    sw $ra,0($sp)       #store return address
    sw $a0, 4($sp)      #store fac_1
    sw $a1, 8($sp)      #store fac_2
    divu $a1, $t0       #div fac_2 by 2
    mflo $a1        #store quotient in $a1
    mfhi $a2        #store remainder in $a2
    sw $a2, 12($sp)     #store remainder on stack


    multu $a0, $t0      #multiply fac_1 by 2
    mflo $a0

    beq $a1, $t6, return    #base case

    jal egypt       #call egypt recursively

addingup:       
    lw $a0, 4($sp)      #load values from stack
    lw $a1, 8($sp)      #   "
    lw $a2, 12($sp)     #   "

    beqz $a2, return    #jump on if remainder is 0

    addu $t7, $t7, $a0  #add if remainder is 1      
return:     

    lw $ra, 0($sp)      #restore return address
    addiu $sp, $sp, 16  #inc stackpointer
    jr $ra

当我尝试使用值 10 和 20 运行程序时，结果（在 $t7 中）为 40，因为未添加最后一个值 160。我怎样才能解决这个问题？

谢谢！

4

1 回答 1

2

jal是指令JUMP AND LINK，这意味着它将下一条指令的地址存储在 r31 中并跳转到给定的标签。您可以说这是在 MIPS 汇编程序中进行子例程调用的（一种/一种）方式。

跳转到 r31 中包含的jr $ra地址，这意味着它返回到后面的指令jal。如您所见，这是在.end.

简而言之，jal就是一个子程序调用，当调用返回时，会执行下面的指令jal。

在您编辑的问题中，您有点奇怪地检查了基本情况，例如；

a = n >> 1;
b = n & 1;
if(a == 0)
   return 0;
...do calculation...

...当一个更好的基本情况是；

if(n == 0)
   return 0;
a = n >> 1;
b = n & 1;
...do calculation...

第一个基本情况的问题是 b 仍然可以为 1 并给出结果，但无论如何您都会返回而不使用该值。

于 2013-05-13T19:03:00.303 回答