NASM Forum > Programming with NASM

can somebody help me figure out fibonacci recurse?

(1/1)

sphinx:
below is my implementation, when I send 10 to the param, it returns 8.
I can't figure out what's wrong.

`asm
global fib

section .text

fib:
cmp rdi, 1              ; if less equal than 1
jle done                ; return

dec rdi                 ; n-1
push rdi                ; push n-1
call fib                ; calculate f(n-1)
mov rcx, rax            ; get f(n-1) results and save to rcx
pop rdi                 ; restore n-1

dec rdi                 ; n-2
push rdi                ; push n-2
call fib                ; calculate f(n-2)
add rax, rcx            ; calulate f(n-1) + f(n-2)
pop rdi                 ; restore n-2

done:
mov rax, rdi
ret
`

Frank Kotler:
Hi sphinx,

Welcome to the Forum.

The "call" instruction pushes the return address onto the stack. So "pop rdi" gets the return address! Old rdi is at "rsp + 8". So "mov rdi , [rsp + 8] " is probably what you want.

Best,
Frank

sphinx:
Thanks for you reply. You said [ "pop rdi" will gets the return address!] , but I found [pop rdi] actually works well.
I am new to NASM or assembly, please make sure you didn't miss something.
after some googling, I figured out what's wrong.
first, I did not save rcx, so its changed during recurse.
second, I forget ret after add f(n-1) and f(n-2).

now it works.

`asm
global fib

section .text

fib:
cmp rdi, 1              ; if less than 1
jle done                ; return

; calculate f(n-1)
dec rdi                 ; n-1
push rdi                ; push n-1
call fib                ; calculate f(n-1)
mov rcx, rax            ; get f(n-1) results and save to rcx
pop rdi                 ; restore n-1

; calculate f(n-2)
push rcx                ; save rcx
dec rdi                 ; n-2
push rdi                ; push n-2
call fib                ; calculate f(n-2)
pop rdi                 ; restore n-2
pop rcx                 ; restore rcx
add rax, rcx            ; calulate f(n-1) + f(n-2)
ret

done:
mov rax, rdi
ret
`

Frank Kotler:
Okay. My memory's all shot. Sorry.

Best,
Frank

fredericopissarra:
A little better approach:

--- Code: ---; fib.asm
bits  64
default rel

section .text

global fib

; unsigned int fib( unsigned int n );
;
; Input: EDI = n (n >= 1)
; Output: EAX (fibonacci number).
align 4
fib:
; Preserve RBP and RBX (SysV ABI).
push  rbp
push  rbx

mov ebp, 1

cmp edi, 3
jb  .exit

mov ebx, edi
mov ebp, 1

align 4
.loop:
lea   edi, [rbx - 1]
call  fib
sub   ebx, 2
ja    .loop

.exit:
mov eax, ebp

; Restore RBP and RBX (SysV ABI).
pop rbx
pop rbp

ret
--- End code ---
Test code:

--- Code: ---/* test.c */
#include <stdio.h>

extern unsigned int fib( unsigned int );

int main( void )
{
unsigned int i;

for ( i = 1; i <= 10; i++ )
printf( "%u ", fib(i) );
putchar( '\n' );
}
--- End code ---