MIPS汇编斐波那契函数输入>1时算术溢出问题求助

问题根源 #

你的代码中斐波那契递推逻辑完全错误，导致数值以错误的指数级增长，远快于正常斐波那契序列，因此输入大于1的正整数时很快触发算术溢出。具体错误在loop段：

add $s1, $s1, $s0  # 错误：这不是斐波那契的递推式
move $s0, $t0
addi $s0, $s0, -1

这段代码的计算逻辑不符合F(n) = F(n-1) + F(n-2)的定义，反而会让数值迅速膨胀，比如输入2时就会计算出错误结果并触发溢出。

修正后的代码 #

以下是修复逻辑后的完整代码，同时保留你定义的F(0)=F(1)=1规则，以及$v0返回合法性、$v1返回结果的约定：

.data

newline:
  .asciiz "\n"

str0:
  .asciiz "Enter a positive integer: "

str1:
  .asciiz "ERROR\n"

str2:
  .asciiz "Result: "

.text

fibonacci:
  addi $sp, $sp, -12
  sw $ra, 8($sp)
  sw $s0, 4($sp)
  sw $s1, 0($sp)
  
  move $s0, $a0       # s0 = n
  li $s1, 1           # s1 = F(n)，初始为F(0)或F(1)的值
  
  # 处理n=0或n=1的情况
  ble $s0, 1, exit_fib
  
  # 初始化递推变量：F(n-1)=1, F(n-2)=1
  li $t0, 1           # t0 = F(k-1)
  li $t1, 1           # t1 = F(k-2)
  addi $s0, $s0, -2   # 从n=2开始循环，需要循环n-2次

loop_fib:
  add $s1, $t0, $t1   # F(k) = F(k-1) + F(k-2)
  move $t1, $t0       # 更新F(k-2)为原来的F(k-1)
  move $t0, $s1       # 更新F(k-1)为当前的F(k)
  addi $s0, $s0, -1
  bgtz $s0, loop_fib  # 循环直到次数耗尽

exit_fib: 
  move $v1, $s1
  lw $ra, 8($sp)
  lw $s0, 4($sp)
  lw $s1, 0($sp)
  addi $sp, $sp, 12
  
  # 处理输入合法性
  bltz $a0, negative_case
  li $v0, 1
  j return_fib

negative_case:
  li $v0, 0
  j return_fib

return_fib:
  jr $ra


.globl main
main:
  # 提示输入
  li $v0, 4
  la $a0, str0
  syscall

  # 读取输入整数
  li $v0, 5
  syscall
  move $t0, $v0

  # 调用斐波那契函数
  move $s0, $ra
  move $a0, $t0
  jal fibonacci
  move $ra, $s0

  move $t0, $v0
  move $t1, $v1

  # 判断是否合法输入
  beq $t0, $zero, main_failure

main_success:
  # 输出结果
  li $v0, 4
  la $a0, str2
  syscall

  li $v0, 1
  move $a0, $t1
  syscall

  li $v0, 4
  la $a0, newline
  syscall

  b main_return

main_failure: 
  # 输出错误信息
  li $v0, 4
  la $a0, str1
  syscall

main_return:
  jr $ra

关键改动说明 #

1. 修正递推逻辑：使用$t0和$t1分别保存F(k-1)和F(k-2)，每次循环计算F(k) = F(k-1) + F(k-2)，并更新递推变量，严格符合斐波那契序列的定义。
2. 调整循环次数：对于n>1的情况，需要循环n-2次来计算到F(n)，保证结果正确。
3. 可读性优化：重命名部分标签（如loop改为loop_fib），让代码逻辑更清晰。

额外说明 #

斐波那契序列本身增长很快，在MIPS 32位整数环境下，当n约为46时，F(n)就会超过2^31-1的上限，仍然会触发算术溢出。如果需要处理更大的数值，需要使用64位寄存器或实现大数运算，但这超出了当前问题的修复范围。

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