彙編中的斐波那契實現給出了意想不到的結果

Question

我試圖寫一個彙編代碼版本的斐波那契給出第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); 
} 

Answer 1

的問題是，你需要更加小心跨過遞歸調用寄存器使用。

您的代碼假設%edx在第二次通話中保留其價值。

但是，情況並非如此，因爲_fibonacci更改了它。

Answer 2

您的遞歸調用是破壞%edx。您需要在您的開場白pushl %edx和popl %edx在postlogue，像這樣：

.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