斐波那契的汇编程序

Question

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

编写一个典型的 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代表"branch if not equal"。

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

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。

斐波那契的汇编程序

assembly program for Fibonacci

assembly

fibonacci

risc