MIPS code I was trying to follow
I am trying to convert recursive fibonacci code into arm assembly but I am running into issues. When running my arm assembly, the final value of the sum is 5 when it should be 2. It seems as though my code loops but maybe one too many times. Any help would be much appreciated as I am new to this.
n: .word 3
_start:
LDR R0, n //n
MOV R2, #0
MOV R1, #0
BL fib
B end
fib:
PUSH {R0, R1, LR}
CMP R0, #0
BNE test2 //if n>0 go to test2
//R2 = sum
ADD R2, #0 //else add 0 to sum
B rtn
test2:
CMP R0, #1
BNE gen // if n> 1 go to gen
ADD R2, #1 // else add 1 to sum
B rtn
gen:
SUB R0, R0, #1 // n-1
BL fib
MOV R1, R0 //copy fib(n-1)
SUB R0, R0, #1 //n-2
BL fib
ADD R2, R2, R1 //fib(n-1) fib(n-2)
rtn:
POP {R0, R1, LR}
BX LR
end:
B end
CodePudding user response:
This is what your code is doing, and below is a test run. This simply isn't a usual recursive fibonacci.
#include <stdio.h>
void f ( int );
int R2 = 0;
int main () {
for ( int i = 0; i < 10; i ) {
R2 = 0;
f ( i );
printf ( "f ( %d ) = %d\n", i, R2 );
}
}
void f ( int n ) {
if ( n == 0 ) { R2 = 0; return; }
if ( n == 1 ) { R2 = 1; return; }
f ( n-1 );
f ( n-2 );
R2 = n-1;
}
f ( 0 ) = 0
f ( 1 ) = 1
f ( 2 ) = 2
f ( 3 ) = 5
f ( 4 ) = 10
f ( 5 ) = 19
f ( 6 ) = 34
f ( 7 ) = 59
f ( 8 ) = 100
f ( 9 ) = 167
Either you started with a broken Fibonacci algorithm, or substantially changed it going to assembly. I don't know how this can be fixed, except by following a working algorithm.
CodePudding user response:
Note that in the C code the only addition is in the fib(n-1) fib(n-2)
. In particular the special cases just do return 0;
and return 1;
respectively. Thus your else add 0/1 to sum
lines are wrong. You should replace your additions with moves.
Also, you do MOV R1, R0 //copy fib(n-1)
which is incorrect because the fib(n-1)
has been returned in R2
not R0
. That should be MOV R1, R2
.
With these changes the code works, even if it is slightly non-standard.