can somebody help me figure out fibonacci recurse?

[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: [Select]

; 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
  add   ebp, eax      ; Accumulate.
  sub   ebx, 2
  ja    .loop

.exit:
  mov eax, ebp

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

  retTest code:

Code: [Select]

/* 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' );
}Compiling, linking and testing:

Code: [Select]

$ cc -c -o test.o test.c
$ nasm -felf64 -o fib.o fib.asm
$ cc -o test test.o fib.o
$ ./test
1 1 2 3 5 8 13 21 34 55