基于MIPS的递归模幂运算程序开发：JAL指令调用位置困惑

需求说明 #

编写MIPS汇编程序，提示用户输入三个正整数x、n、p，计算并输出x^n mod p，要求采用**递归版模幂运算（Modular Exponentiation）**实现。

当前代码 #

.text
main: 
      sub  $sp,$sp,4                # save return address on stack
      sw   $ra, 0($sp)
    
    li   $v0, 4             # prompt user for int x
    la   $a0, S1
      syscall

      li   $v0, 5                  # read int
      syscall
      move $s0, $v0                # cin >> x //and store x in $s0

    li   $v0, 4             # prompt user for int n
    la   $a0, S1
      syscall

      li   $v0, 5                  # read int
      syscall
      move $s1, $v0                # cin >> n //and store n in $s1
    
    li   $v0, 4             # prompt user for int p
    la   $a0, S1
      syscall

      li   $v0, 5                   # read int
      syscall
      move $s2, $v0                 # cin >> p //and store p in $s2

        
    li $t0, 0               # return value 
    li $t1, 2               # constant 2
    li $t2, 0               # variable y

    beq $s0, $zero, L1      # if x == 0, return 1
    beq $s1, $zero, L2      # if n is 0, return 0

    jal evenMod

L0: 
    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

L1:         
    li $v0, 4
    la $a0, S3
    syscall
    j L0
    

L2:
    li $v0, 4
    la $a0, S4
    syscall
    j L0

L3:
    li $v0, 1
    move $a0, $s1
    syscall
    j L0

evenMod:
    
    beq $s0, $zero, L1      # if x == 0, return 1
    beq $s1, $zero, L2      # if n is 0, return 0
    rem $s3, $s1, $t1           # s3 = s1 % 2
    
    bne $s3, $zero, oddMod      # if n%2 != 0, jump to oddMod

    div $s1, $s1, 2         # n = n/2
    mult $t2, $t2           # y = y*y
    rem $t2, $t2, $s2           # y= (y*y)%p
    jal evenMod
    j L3
    
oddMod:
    
    beq $s0, $zero, L1      # if x == 0, return 1
    beq $s1, $zero, L2      # if n is 0, return 0
    
    rem $s3, $s1, $t1           # s3 = s1 % 2
    
    bne $s3, $zero, evenMod     # if n%2 !=0, jump to evenMod

    rem $s3, $s1, $s2           # s3 = s1 % P
    addi $s0, 0             # x stays the same
    add $s1, $s1, -1            # n = n-1
    addi $s2, 0             # p stays the same

    jal oddMod              # call oddmod with updated values
    mult $t2, $t2           # multiply y*y
    rem $t2, $t2, $s2           # y = y%P
    
    j L3
    

.data
S1:
      .asciiz "Enter an integer --> "
S3: 
    .asciiz "0"
S4: 
    .asciiz "1"

问题分析与JAL指令修正 #

当前代码的核心问题并非JAL指令本身，而是递归上下文未保存、模幂逻辑错误以及变量初始化错误，同时JAL的使用场景不符合递归调用规范。以下是具体修正方案：

1. 递归调用核心规则 #

递归调用必须通过JAL指令发起（而非直接跳转），这样才能自动将返回地址存入$ra；同时需要将递归过程中会被修改的寄存器（如$s0-$s2、$ra）压入栈，避免后续调用覆盖原有数据。

2. 模幂运算正确递归逻辑 #

标准递归模幂公式：

pow_mod(x, n, p) = 
    if n == 0: 1
    elif n 为偶数: pow_mod( (x*x) mod p, n/2, p )
    else: ( x * pow_mod(x, n-1, p) ) mod p

3. 修正后的代码（重点标注JAL与栈操作） #

.text
main: 
    sub  $sp, $sp, 16       # 预留栈空间保存ra、s0、s1、s2
    sw   $ra, 0($sp)
    sw   $s0, 4($sp)
    sw   $s1, 8($sp)
    sw   $s2, 12($sp)
    
    li   $v0, 4             # 提示输入x
    la   $a0, S1
    syscall
    li   $v0, 5
    syscall
    move $s0, $v0           # s0 = x

    li   $v0, 4             # 提示输入n
    la   $a0, S1
    syscall
    li   $v0, 5
    syscall
    move $s1, $v0           # s1 = n

    li   $v0, 4             # 提示输入p
    la   $a0, S1
    syscall
    li   $v0, 5
    syscall
    move $s2, $v0           # s2 = p

    jal pow_mod             # 调用递归模幂函数，结果存入v0

    # 输出结果
    li   $v0, 1
    move $a0, $v0
    syscall

L0: 
    lw   $ra, 0($sp)        # 恢复寄存器
    lw   $s0, 4($sp)
    lw   $s1, 8($sp)
    lw   $s2, 12($sp)
    addi $sp, $sp, 16       # 恢复栈指针
    jr   $ra

# 递归模幂函数：输入s0=x, s1=n, s2=p；输出v0=x^n mod p
pow_mod:
    # 保存递归上下文到栈
    sub  $sp, $sp, 16
    sw   $ra, 0($sp)
    sw   $s0, 4($sp)
    sw   $s1, 8($sp)
    sw   $s2, 12($sp)

    # 基准情况：n=0，返回1 mod p
    beq  $s1, $zero, return_1
    # 基准情况：x=0，返回0（兼容非正整数输入）
    beq  $s0, $zero, return_0

    li   $t0, 2
    rem  $t1, $s1, $t0      # t1 = n%2

    # 偶数分支
    beqz $t1, even_case
    # 奇数分支
    j    odd_case

even_case:
    div  $s1, $s1, $t0      # n = n/2
    mult $s0, $s0           # x*x
    mflo $s0
    rem  $s0, $s0, $s2      # x = (x*x) mod p
    jal  pow_mod            # 递归调用pow_mod(x, n/2, p)
    j    return_result

odd_case:
    addi $s1, $s1, -1       # n = n-1
    jal  pow_mod            # 递归调用pow_mod(x, n-1, p)
    # 计算(x * 递归结果) mod p
    mult $v0, $s0           # v0 = v0 * x
    mflo $v0
    rem  $v0, $v0, $s2      # v0 = v0 mod p
    j    return_result

return_1:
    li   $v0, 1
    rem  $v0, $v0, $s2      # 1 mod p
    j    return_result

return_0:
    li   $v0, 0
    j    return_result

return_result:
    # 恢复上下文
    lw   $ra, 0($sp)
    lw   $s0, 4($sp)
    lw   $s1, 8($sp)
    lw   $s2, 12($sp)
    addi $sp, $sp, 16
    jr   $ra

.data
S1: .asciiz "Enter an integer --> "

关键修正点说明 #

• JAL的正确使用：在even_case和odd_case分支中，通过jal pow_mod发起递归调用，自动保存返回地址到$ra，确保递归完成后能回到当前位置继续计算。
• 栈操作规范：每次进入pow_mod函数时，先将$ra、$s0-$s2压入栈，递归返回后再恢复，避免寄存器值被后续调用覆盖。
• 逻辑修正：严格遵循模幂递归公式，偶数分支先计算x*x mod p再递归，奇数分支先递归n-1再乘以x取模。
• 结果传递优化：用$v0传递递归结果，替代原代码中错误初始化的$t2变量。

内容的提问来源于stack exchange，提问作者eswcs