2

I just got a question about the assembly program for Fibonacci sequence. The question is as following : 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.

I received the answer of following:

   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

where # indicates immediate addressing and BNE stands for "branch if not equal".

I do not understand why... Can anyone please explain it to me?

Rietty
  • 1,116
  • 9
  • 24
hmmmmm_computing
  • 23
  • 1
  • 4
  • Looks totally normal to me: keep the last 2 Fib(i) values around in registers to calculate the next one from. If they'd unrolled the loop, you could `x += y` / `y += x`, but with it rolled up you need 2 register-copy instructions. e.g. like this C version: [What's wrong with my MIPS code about finding fibonacci number?](//stackoverflow.com/q/43290402). – Peter Cordes Feb 17 '19 at 22:49
  • 1
    With 3 changes, the codr could handle M >= 0: | LOAD r0,#-1 | LOAD r1,#1 | ... | BNE 4, r2, #-1 | . This is based on Fib(-2) = -1, Fib(-1) = 1, Fib(0) = 0. – rcgldr Feb 18 '19 at 01:47

1 Answers1

3

The code is perfectly correct. Here is a commented version that may answer your questions. 

   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

Note that i never appears, but it is simpler to think of it, instead of k that is decremented.

Alain Merigot
  • 10,667
  • 3
  • 18
  • 31
  • Thanks a lot Alain!Can you please explain why it loads r2 to M?Can we not start with r0 and load it to M?Also I am not quite get what sub r2 r2 #1 means.Do you mind explaining it ?Thanks! – hmmmmm_computing Feb 18 '19 at 15:27
  • First line is just a mean to store in a register the value of k we want. Call it k or M, it does not matter, but we need to get this parameter. `sub r2, r2, #1` is sub(stract) 1 from r2 and store it in r2 and corresponds to r2<-r2-1. – Alain Merigot Feb 18 '19 at 17:39
  • Thanks a lot Alain. Does that mean if I store r0 to M will be ok? Not necessarily r2 to M?So for example, we can do LOAD r0, M LOAD r1, #1 LOAD r2, #1 ? – hmmmmm_computing Feb 18 '19 at 17:48
  • If you want you can do LOAD r9, M LOAD r3, #1 LOAD r7, #1 The reg names do not matter, but you must be coherent. Think of regs as variables in C code. You can use whatever name, but keep the same all over a program. – Alain Merigot Feb 18 '19 at 17:58
  • I think my another question is why subtract 1 from r2? – hmmmmm_computing Feb 18 '19 at 17:59
  • Exact C translation of asm code is: `M=k; f_2=1; f_1=1; do{ k--; f=f_1+f_2; f_2=f_1; f_1=f; } while(k>2); result=f-1; // or f` Without `k--`, you do not exit your loop. – Alain Merigot Feb 18 '19 at 18:29
  • The extract C is not what I am looking for. I am just trying to understand why the final answer in the paper is as what I wrote in the question. I still not quite understand why 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)) – hmmmmm_computing Feb 18 '19 at 21:20
  • My thought is r0 is 1 and r1 is 1. Why it suddenly turns to ADD r3, r0, r1 ; F(i)=F(i-2)+F(i-1) ( r0=F(i-2) and r1=F(i-1))? <---- why is that?When did we change the r0 to F(i-2) and r1 to F(i-1)?) – hmmmmm_computing Feb 18 '19 at 21:22
  • Also why we can not just skip the LOAD r0, r1 ; F(i-2)=r1 (previously F(i-1)) LOAD r1, r3 ; F(i-1)=r3 (just computed F(i)) and just change Store M, r3? – hmmmmm_computing Feb 18 '19 at 21:25