Practice3 Explanation - GawinGowin/libasm GitHub Wiki

Practice3: フィボナッチ数列プログラムの詳細解説

なぜこの練習を行うのか

学習目的

  1. 複雑な再帰アルゴリズムの実装

    • 複数の再帰呼び出しを含む関数
    • 中間結果の管理方法
    • より高度なスタック操作

  2. 制御構造の理解深化

    • 複数の条件分岐
    • レジスタを活用した値の保持
    • 効率的な計算順序

  3. アルゴリズム思考の養成

    • 数学的定義からコード実装への変換
    • 計算量を意識したプログラミング
    • デバッグ技術の向上

コード詳細解析

; practice3.s - フィボナッチ数列
section .text
    global fibonacci

fibonacci:
    ; 引数: rdi (n)
    ; 戻り値: rax
    cmp rdi, 2
    jl .base_case
    
    push rbx        ; rbxレジスタを保存（呼び出し規約）
    push rdi
    dec rdi
    call fibonacci
    mov rbx, rax
    
    pop rdi
    sub rdi, 2
    call fibonacci
    add rax, rbx
    pop rbx         ; rbxレジスタを復元
    ret

.base_case:
    mov rax, rdi
    ret

フィボナッチ数列の数学的定義

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)  (n >= 2)

関数構造の解説

ベースケース判定

cmp rdi, 2              ; n と 2 を比較
jl .base_case           ; n < 2 なら .base_case へ

判定ロジック:

  • n < 2 の場合: F(0) = 0, F(1) = 1
  • n >= 2 の場合: 再帰計算が必要

ベースケース処理

.base_case:
    mov rax, rdi        ; F(0) = 0, F(1) = 1
    ret

重要なポイント:

  • F(0) = 0, F(1) = 1 を同時に処理
  • 引数値をそのまま戻り値として使用

再帰処理の詳細解析

第1回目の再帰呼び出し

push rbx                ; rbxレジスタを保存（呼び出し規約）
push rdi                ; 元の n を保存
dec rdi                 ; n-1 を計算
call fibonacci          ; fibonacci(n-1) を呼び出し
mov rbx, rax            ; 結果を rbx に保存

処理フロー:

  1. rbx レジスタを保存（System V AMD64 ABI準拠）
  2. 現在の引数 n をスタックに退避
  3. n-1 を計算して fibonacci を再帰呼び出し
  4. fibonacci(n-1) の結果を rbx に保存

第2回目の再帰呼び出し

pop rdi                 ; 元の n を復元
sub rdi, 2              ; n-2 を計算
call fibonacci          ; fibonacci(n-2) を呼び出し
add rax, rbx            ; F(n-1) + F(n-2) を計算
pop rbx                 ; rbxレジスタを復元
ret                     ; 結果を返す

処理フロー:

  1. スタックから元の n を復元
  2. n-2 を計算して fibonacci を再帰呼び出し
  3. fibonacci(n-2) の結果（rax）と fibonacci(n-1) の結果（rbx）を加算
  4. rbx レジスタを復元（呼び出し規約準拠）

実行フローの追跡

fibonacci(4) の実行例

fibonacci(4)
├── fibonacci(3)
│   ├── fibonacci(2)
│   │   ├── fibonacci(1) → 1
│   │   └── fibonacci(0) → 0
│   │   └── 1 + 0 = 1
│   └── fibonacci(1) → 1
│   └── 1 + 1 = 2
└── fibonacci(2)
    ├── fibonacci(1) → 1
    └── fibonacci(0) → 0
    └── 1 + 0 = 1
└── 2 + 1 = 3

詳細なスタック変化

1. fibonacci(4) 開始
   - rdi = 4, スタック: []

2. 第1回目再帰前
   - push rbx, スタック: [rbx_original]
   - push 4, スタック: [rbx_original, 4]
   - call fibonacci(3)

3. fibonacci(3) 内で第1回目再帰前
   - push rbx, スタック: [rbx_original, 4, rbx_3]
   - push 3, スタック: [rbx_original, 4, rbx_3, 3]
   - call fibonacci(2)

4. fibonacci(2) 内で第1回目再帰前
   - push rbx, スタック: [rbx_original, 4, rbx_3, 3, rbx_2]
   - push 2, スタック: [rbx_original, 4, rbx_3, 3, rbx_2, 2]
   - call fibonacci(1) → return 1

5. fibonacci(2) 内で第2回目再帰前
   - pop 2, スタック: [rbx_original, 4, rbx_3, 3, rbx_2]
   - call fibonacci(0) → return 0
   - add: 1 + 0 = 1
   - pop rbx, スタック: [rbx_original, 4, rbx_3, 3]
   - return 1

... (以下同様)

学習効果

この練習で身につくスキル

  1. 高度なスタック管理

    • 複数の値の同時保存・復元
    • 中間結果の適切な管理
    • スタック領域の効率的な使用

  2. レジスタ活用技術

    • 複数レジスタでの値保持
    • 一時的な値の格納方法
    • レジスタ間でのデータ移動

  3. 呼び出し規約の理解

    • System V AMD64 ABI準拠
    • 呼び出し元保存レジスタの管理
    • 適切なレジスタ保存・復元

  4. アルゴリズム実装能力

    • 数学的定義の正確な翻訳
    • 効率性を考慮した実装
    • デバッグ困難なコードの作成・修正

パフォーマンス分析

計算量の問題

fibonacci(n) の呼び出し回数:
F(5): 15回
F(10): 177回
F(20): 21,891回
F(30): 2,692,537回

指数関数的増加:

  • 時間計算量: O(φⁿ) where φ ≈ 1.618
  • 空間計算量: O(n) （スタック深度）

最適化への発展

1. 末尾再帰最適化版

fibonacci_iter:
    ; 引数: rdi (n), rsi (a=0), rdx (b=1)
    test rdi, rdi
    jz .return_a
    
    dec rdi
    mov rax, rsi
    add rax, rdx
    mov rsi, rdx
    mov rdx, rax
    jmp fibonacci_iter

.return_a:
    mov rax, rsi
    ret

2. メモ化（動的プログラミング）

; 配列を使用した結果キャッシュ
; memo[n] = fibonacci(n) の結果を保存

よくある間違いとデバッグ

1. レジスタ管理ミス（修正済み）

; 間違い: rbx の値が上書きされる
call fibonacci
mov rbx, rax        ; 第1回目の結果保存
call fibonacci      ; rbx が破壊される可能性
add rax, rbx        ; 間違った値を使用

; 正しい実装: rbx レジスタの保存・復元
push rbx            ; rbx を保存
call fibonacci
mov rbx, rax        ; 第1回目の結果保存
call fibonacci      ; rbx は保護されている
add rax, rbx        ; 正しい値を使用
pop rbx             ; rbx を復元

2. スタック不均衡

; 間違い: 条件によってPUSH/POPが不一致
cmp rdi, 2
jl .base_case
push rdi
; .base_case でも pop が必要？（NO）

3. ベースケース設定ミス

; 間違い: F(0) = 1 として実装
cmp rdi, 1
jle .base_case
.base_case:
    mov rax, 1      ; F(0) = 1 は間違い

発展的な実装課題

この理解を基に以下にチャレンジできます：

  1. 他の数列実装

    • トリボナッチ数列
    • カタラン数
    • ルーカス数

  2. 最適化手法

    • 高速行列べき乗法
    • ビネットの公式実装
    • メモ化技法

  3. 大数演算

    • 64bit を超える値の処理
    • 多倍長整数演算

この練習により、複雑な再帰アルゴリズムの実装能力が身につき、アルゴリズムの効率性を意識したプログラミングができるようになります。

コンパイル方法

必要なツール

  • NASM（Netwide Assembler）
  • GCC（GNU Compiler Collection）

コンパイル手順

# アセンブリファイルをオブジェクトファイルにコンパイル
nasm -f elf64 practice3.s -o practice3.o

# Cファイルとアセンブリオブジェクトファイルをリンクして実行ファイルを作成
gcc practice3.c practice3.o -o practice3

# 実行
./practice3

テストコード

以下のテストコードを practice3.c として保存してください：

#include <stdio.h>

// Declaration of the assembly function
extern long fibonacci(long n);

int main() {
    printf("Fibonacci sequence test:\n");
    
    // Test cases for fibonacci function
    for (int i = 0; i <= 10; i++) {
        long result = fibonacci(i);
        printf("fibonacci(%d) = %ld\n", i, result);
    }
    
    // Additional test cases
    printf("\nAdditional test cases:\n");
    printf("fibonacci(15) = %ld\n", fibonacci(15));
    printf("fibonacci(20) = %ld\n", fibonacci(20));
    
    return 0;
}

期待される出力

Fibonacci sequence test:
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8
fibonacci(7) = 13
fibonacci(8) = 21
fibonacci(9) = 34
fibonacci(10) = 55

Additional test cases:
fibonacci(15) = 610
fibonacci(20) = 6765
⚠️ **GitHub.com Fallback** ⚠️