Fibonacci implementation in assembly yields unexpected results

Question

I am trying to write a version of the Fibonacci assembly code that gives the nth Fibonacci number and returns it.

For some reason, he has problems with saving the return value of Fibonacci numbers and adding them.

I want him to print the nth Fibonacci number.

I made some changes to my code, now it is still incorrect, but it is closer. Now he tells me that the 11th fibonacci number is 48. Still not true, but do we get somewhere to the right?

.text .globl _fibonacci _fibonacci: pushl %ebp movl %esp,%ebp push %esi movl 8(%ebp),%esi cmp $1,%esi jle BASE sub $1,%esi push %esi call _fibonacci add $4,%esp movl %eax,%edx sub $1,%esi push %esi call _fibonacci add $4,%esp add %eax,%edx movl %edx,%eax DONE: pop %esi pop %ebp ret BASE: mov $1,%eax jmp DONE 

I call this assembly code using C:

 #include <stdio.h> int fibonacci(int n); int main(void){ int n=111; int x=fibonacci(n); printf("The %d fibonaacci number is %d\n",n,x); } 

Answer 1

The problem is that you need to be more careful with using registers in all recursive calls.

Your code assumes that %edx stores its value in the second call.

However, this is not so, because _fibonacci changes it.

Answer 2

Your recursive calls are clobbering %edx . You need pushl %edx in your prolog and popl %edx in your postlogue, for example:

 .text .globl _fibonacci /* fib(n) = fib(n-1) + fib(n-2) */ _fibonacci: pushl %ebp movl %esp,%ebp pushl %esi pushl %edx /* <-- PUSH TO SAVE BEFORE CLOBBERING */ movl 8(%ebp),%esi /* 0th and 1st numbers are defined to be 1. */ cmpl $1,%esi jle BASE /* find fib(n-1) */ subl $1,%esi pushl %esi call _fibonacci addl $4,%esp movl %eax,%edx /* <-- %edx CLOBBERED! */ /* find fib(n-2) */ subl $1,%esi pushl %esi call _fibonacci addl $4,%esp addl %edx,%eax DONE: popl %edx /* <-- POP TO RESTORE AFTER CLOBBERING */ popl %esi popl %ebp ret BASE: movl $1,%eax jmp DONE 

Using this driver:

 // BUILD -arch i386 ONLY // clang -arch i386 fib.s fibo.c -o fibo #include <stdio.h> int fibonacci(int n); void Test(int i) { int r = fibonacci(i); printf("fib(%d) -> %d\n", i, r); } int main(void){ for (int i = 0; i < 10; ++i) { Test(i); } return 0; } 

The test run is as follows:

 $ ./fibo fib(0) -> 1 fib(1) -> 1 fib(2) -> 2 fib(3) -> 3 fib(4) -> 5 fib(5) -> 8 fib(6) -> 13 fib(7) -> 21 fib(8) -> 34 fib(9) -> 55