斐波那契的组装程序

Question

我刚刚收到一个关于斐波那契数列汇编程序的问题。问题如下： 斐波那契数列F定义为F(1) = F(2) = 1和n ≥ 2，F(n + 1) = F(n) + F(n − 1)即，(n + 1)th值由nth值和(n − 1)th值之和给出。

1. 编写一个典型的RISC机器汇编程序，用于计算kth值F(k)，其中k是一个大于2从内存位置加载M的自然数，并将结果存储在内存位置M。

我收到了以下答案：

LOAD r2, M
LOAD r0, #1
LOAD r1, #1
4: SUB r2, r2, #1
ADD r3, r0, r1
LOAD r0, r1
LOAD r1, r3
BNE 4, r2, #2 // jump to instruction 4 if r2 is not equal to 2
STOR M, r1

其中 # 表示即时寻址，BNE 代表"分支，如果不相等"。

我不明白为什么...谁能向我解释一下？

Answer 1

代码是完全正确的。这是一个评论版本，可以回答您的问题。

LOAD r2, M     ; R2 -> k (as F(K) has to be computed)
LOAD r0, #1    ; F(1)=1 -> r0 
LOAD r1, #1    ; F(2)=1 -> r1 
; As F(1) and F(2) are already computed, we start at i=2
; During al the computation of F(i) r1==F(i-1) and r0== F(i-2)
4: SUB r2, r2, #1 ; k-- 
ADD r3, r0, r1 ; F(i)=F(i-2)+F(i-1)
; F(i) computed, prepare next iteration (implicitely i++)
LOAD r0, r1    ; F(i-2)=r1 (previously F(i-1))
LOAD r1, r3    ; F(i-1)=r3 (just computed F(i))
BNE 4, r2, #2 // jump to instruction 4 if r2 (k) is not equal to 2
; because we have started at i==2 we must perform
; k-2 iterations. 
STOR M, r1

请注意，i 从未出现过，但考虑起来更简单，而不是递减的 k。