Question

The Fibonacci sequence F is defined as F(1) = F(2) = 1 and for n>= 2,
F(n + 1) = F(n) + F(n − 1)
i.e., the (n + 1)th value is given by the sum of the nth value and the (n − 1)th value.

1. Write an assembly program typical of RISC machines for computing the kth value F(k), where k is a natural number greater than 2 loaded from a memory location M, and storing the result at memory location M.

Use the Instruction Set Architecture below

Instruction Set Architecture
We present a list of instructions typical of a RISC (reduced instruction set computer)
machine. In data-movement and control instructions, the addresses may be immediate #X,
direct (memory) M, indirect (memory) [M], register r, or register indirect [r] addresses.
Data-processing instructions use immediate or register addressing. PC is the programme
counter and a <- b indicates that the value of b is placed in a.
LOAD a, b a <- b
STOR a, b a <- b
ADD a, b, c a <- b + c
SUB a, b, c a <- b - c
MUL a, b, c a <- b * c
DIV a, b, c a <- b / c
AND a, b, c a <- b & c
OR a, b, c a <- b | c
NOT a, b a <- !b
ASH a, b, c a <- b arithmetically shifted by c positions
LSH a, b, c a <- b logically shifted by c positions
BR a PC <- a
BEQ a, b, c PC <- a if b is equal to c
BNE a, b, c PC <- a if b is not equal to c
BLT a, b, c PC <- a if b is less than c
BGT a, b, c PC <- a if b is greater than c
BLE a, b, c PC <- a if b is less than or equal to c
BGE a, b, c PC <- a if b is greater than or equal to c
Most instructions have oating-point versions when special oating-point registers are used
(but we will not need these).
Most architectures use two addresses, where the first (or second) argument serves both
as the target and one of the sources, e.g., ADD a, b means a <- a + b. For branch instructions, BR X means to jump to instruction X (i.e., load the address of instruction x into PC).
We will use a ve-stage pipeline: IF (instruction fetch), ID (instruction decode), RR
(register read), EX (execute instruction), WB (write back result). We will assume that
for data-movement instructions the data transfer between the CPU and main memory
happens in the execute stage. Note that for some instructions (e.g., LOAD r, #X) some of
the pipeline stages (e.g., RR) are not needed.

Solution:
1. 1. LOAD r2, M
2. LOAD r0, #1
3. LOAD r1, #1
4. SUB r2, r2, #1
5. ADD r3, r0, r1
6. LOAD r0, r1
7. LOAD r1, r3
8. BNE 4, r2, #2 // jump to instruction 4 if r2 is not equal to 2
9. STOR M, r1
where # indicates immediate addressing and BNE stands for “branch if not equal”.

According to the solution above, how the solution will be for this function?

The function F is dened as F(1) = F(2) = F(3) = 1 and for n>= 3,
F(n + 1) = F(n) + (F(n - 1) x F(n - 2))
i.e., the (n + 1)th value is given by the sum of the nth value and the
multiplication of the (n - 1)th and (n - 2)th values.

Answer 1

The solution to the above problem will be :

1. LOAD r3, M //load n from the memory location M in r3 register

2. LOAD r0, #1 //load 1 into r0 register

3. LOAD r1, #1 //load 1 into r1 register

4. LOAD r2, #1 //load 1 into r2 register

5. SUB r3, r3, #1

6.MUL r5,r0,r1 //mul f(n-1) and f(n-2) and loading into r5

7.ADD r6,r2,r5 //add r5 with f(n) and saving into r6

8.LOAD r0, r1 //loading the values one step further in the steps(8,9,10)

9.LOAD r1, r2

10.LOAD r2, r6

11.BNE 5, r3, #3 //jump to instruction 5 if r3 is not equal to 3

12.STOR M,r2 //storing answer into the Location M