Реализация Фибоначчи в сборке дает неожиданные результаты

Я пытаюсь написать версию кода Фибоначчи на ассемблере, которая дает n-е число Фибоначчи и возвращает его.

По какой-то причине у него возникают проблемы с сохранением возвращаемого значения чисел Фибоначчи и их добавлением.

Я хочу, чтобы он напечатал n-е число Фибоначчи.

Я внес некоторые изменения в свой код, теперь он все еще неверен, но он ближе. Теперь он говорит мне, что 11-е число Фибоначчи равно 48. Все еще неверно, но мы в чем-то правы?

.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

Я вызываю этот ассемблерный код, используя 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);
}

x86 assembly fibonacci
person NONE    schedule 22.10.2011    source источник
comment
этот код имеет экспоненциальный асимптотический рост... не делайте этого.   -  person Karoly Horvath    schedule 23.10.2011
comment
время работы не имеет для меня большого значения, я просто хочу что-то, что дает правильный результат   -  person NONE    schedule 23.10.2011

Ответы (2)


arrow_upward
1
arrow_downward

Проблема в том, что вам нужно быть более осторожным с использованием регистров при рекурсивных вызовах.

В вашем коде предполагается, что %edx сохраняет свое значение при втором вызове.

Однако это не так, потому что _fibonacci меняет его.

person Matthew Slattery    schedule 23.10.2011

arrow_upward
2
arrow_downward

Ваши рекурсивные вызовы затирают %edx. Вам нужно pushl %edx в прологе и popl %edx в постлоге, например:

.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

Используя этот драйвер:

// 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;
}

Тестовый запуск выглядит так:

$ ./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
person Jeremy W. Sherman    schedule 23.10.2011
comment
Я новичок в сборке, но если бы я изменил popl %esi и %epb в DONE, чтобы оставить. А потом subl $2, esi найти n-2, получится или нет? - person fangio; 12.03.2016
comment
@fangio Почему бы тебе не попробовать и не посмотреть? - person Jeremy W. Sherman; 12.03.2016