Программа сборки для Фибоначчи - PullRequest
Новая
       58

Программа сборки для Фибоначчи

0 голосов
/ 18 февраля 2019

Я только что получил вопрос о программе сборки для последовательности Фибоначчи.Вопрос заключается в следующем: последовательность Фибоначчи 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 означает "ветвь, еслине равны ".

Я не понимаю, почему ... Может кто-нибудь объяснить мне?

1 Ответ

0 голосов
/ 18 февраля 2019

Код совершенно правильный.Вот закомментированная версия, которая может ответить на ваши вопросы.

   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

Обратите внимание, что я никогда не появляюсь, но проще думать об этом, чем уменьшенное k.

...