## 1. What is Fibonacci sequence
- Fibonacci là một dãy số tăng dần đến vô cùng với điều kiện:
- Dãy (thường) bắt đầu với 0 và 1
- Số đằng sau bằng tổng hai số liền kề trước nó
- Ví dụ: 0, 1, 1, 2, 3, 5, 8, ...
- Trong bài này mình sẽ lấy dãy bắt đầu từ 0, nói cách khác, số fibonacci đầu tiên là 0, thứ hai và ba là 1, thứ 4 là 2, ...
## 2. Nth Fibonacci number
- Một bài toán kinh điển mà ai học lập trình cũng từng kinh qua chính là tìm số fibonacci thứ n. Về cơ bản, bài toán này không khó, nó giúp ta thực hành các kiến thức về mảng và đệ quy dễ hơn. Sử dụng mảng và đệ quy cũng chính là hai cách tìm số fibonacci thứ n thường gặp, chi tiết các bạn có thể xem ở [đây](https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/).
### Algorithm
- Mình dùng mảng cho thuật toán trong C, đơn giản vì nó dễ cài đặt và dễ theo dõi.
- Thuật toán cho Assembly mà mình sử dụng ở bài này là vòng lặp tối ưu không gian, không phải mảng, vì trong assembly, địa chỉ của mảng khá phức tạp, bên cạnh đó còn cần phải tối ưu không gian để lưu các số fibonacci lớn. Đôi khi sẽ gặp phải trường hợp define thiếu bộ nhớ trong `section .bss` nên mình bỏ qua luôn.
#### Code in C
- Code mình sử dụng để tìm số fibonacci thứ `n`, với `n` không vượt quá 92 vì vượt ngưỡng lưu được của một số long long:

#include <stdio.h>

int main(){
    long long n;
    scanf("%lld", &n);
    long long a[n];
    for(int i=0; i<n; i++){
        if(i<=1) a[i] = i;
        else{
            a[i] = a[i-1] + a[i-2];
        }
        printf("%lld ", a[i]);
    }
    return 0;
}

- Để thuận tiện cho việc theo dõi dãy fibonacci, mình chọn in ra `n` số đầu tiên
- Bên cạnh đó cũng có thể sử dụng vòng lặp để tối ưu không gian hơn:

#include <stdio.h>

long long nthFibonacci(int n) {
    if (n <= 1) return n;

    long long sum = 0;
    long long num1 = 1;
    long long num2 = 0;

    for (int i = 2; i <= n; i++) {
        sum = num1 + num2;
        num1 = num2;
        num2 = sum;
    }

    return sum;
}

int main() {
    int n;
    scanf("%d", &n);
    long long result = nthFibonacci(n);
    printf("%lld\n", result);
    return 0;
}

#### Code in Assembly
- Thực ra đối với code Assembly, mình đã ánh xạ từ code C vòng lặp ở trên. Tuy nhiên, cần phải lưu ý, để tìm các số fibonacci với `n` lớn, chúng ta cần thuật toán để handle số lớn. Đó là xử lí tổng và xử lí dấu bằng.
- Vì tính chất của dãy fibonacci, hiển nhiên khi tìm số thứ `n` quá lớn so với số `long long` là 8 bytes, chúng ta cần hàm `sumBigNum` mình đã nói ở [bài trước](https://hackmd.io/@Zupp/Asm104#4-Updating).
- Do trong vòng lặp của code C có dịch chuyển `num1 = num2; num2 = sum`, chúng ta không thể tùy tiện sử dụng lệnh `mov` kiểu:

mov eax, [num2]
mov [num1], eax

mov eax, [sum]
mov [num2], eax

vì các thanh ghi trong x86 chỉ lưu được đến 32 bit, tức 4 byte, tương đương một số `int`, thành ra việc sử dụng `sumBigNum` của mình sẽ cho ra số sai nếu kết quả quá lớn. Thay vào đó, mình sử dụng một thuật toán khác, tạm gọi là `transfer` (giống với [code của anh Sơn](https://github.com/SonVH2511/trainingKCSC/blob/main/TASK1_FIB%2CSORT%2CBIGNUM/FibonacciPrime.asm))

- Ý tưởng là hai số bằng nhau khi và chỉ khi tất cả các chữ số của chúng giống nhau, tuy nhiên nếu code như anh Sơn thì chỉ `transfer` được 150 chữ số. Vì thế mình sử dụng byte NULL để kết thúc số BigNum của mình một cách linh hoạt hơn. Code của mình như sau:

; Transfering step
push edx        ; backup n
; num1 = num2
xor esi, esi
transfer1:
    mov dl, [num2 + esi]
    mov [num1 + esi], dl
    inc esi
    cmp dl, 0
    jne transfer1

; num2 = sum
xor esi, esi
transfer2:
    mov dl, [sum + esi]
    mov [num2 + esi], dl
    inc esi
    cmp dl, 0
    jne transfer2

pop edx         ; restore n

- Đó là toàn bộ ý tưởng của mình cho bài toán tìm số fibonacci thứ `n`, dưới đây là code:

global _start
%include "../Function/functions.asm"

section .bss
    n: resb 10
    num1: resb 100
    num2: resb 100
    sum: resb 105

section .data
    input: db "Input the n to find nth fibonacci number: ", 0
    output: db "That nth fibonacci number is: ", 0

section .text
_start:
    lea esi, [input]
    call sPrint         ; Print input

    lea esi, [n]
    call sScan          ; Get input which is n

    lea esi, [n]
    call strToInt       ; convert n to int
    pop edx             ; [esp] is n -> edx holds n
    
    cmp edx, 1          ; if finding first fibo num
    je case1
    cmp edx, 2          ; if finding second fibo num
    je case2
    jmp case3           ; >= 3rd fibo num

    case1:              ; first fibo num
        mov al, "0"
        mov [sum], al
        jmp finished

    case2:              ; second fibo num
        mov al, "1"
        mov [sum], al
        jmp finished

    case3:              ; from third num 
        mov ecx, 0      ; i = 0
        sub edx, 2      ; n -= 2 because I have skipped the first two values on case 1 and case 2
        ; Prepare initial fibo nums
        mov al, "0"
        mov [num1], al
        mov al, "1"
        mov [num2], al

        fiboLoop:
            mov [sum], byte 0           ; clear result
            push num1                   ; format of sumBigNum
            push num2                   ; format of sumBigNum
            push sum                    ; format of sumBigNum
            call sumBigNum              ; sumBigNum(*dest, *num2, *num1)
            ; Now the first three values of the stack are
            ; [sum]
            ; [num2]
            ; [num1]
            add esp, 0xc    ; skip the old results stored on stack bc it messes things up
            
            ; Transfering step
            push edx        ; backup n
            ; num1 = num2
            xor esi, esi
            transfer1:
                mov dl, [num2 + esi]
                mov [num1 + esi], dl
                inc esi
                cmp dl, 0
                jne transfer1
            
            ; num2 = sum
            xor esi, esi
            transfer2:
                mov dl, [sum + esi]
                mov [num2 + esi], dl
                inc esi
                cmp dl, 0
                jne transfer2

            pop edx         ; restore n for continuing the loop
            inc ecx         ; i++
            cmp ecx, edx    ; cmp i with n
            jne fiboLoop
            
    finished:
        lea esi, [output]
        call sPrint

        lea esi, [sum]
        call sPrint

    call quit

- Test validity:
- Check lại với [link này](https://www.math.net/list-of-fibonacci-numbers) để kiểm tra kết quả. Lưu ý rằng họ lấy số fibo đầu tiên là `1`, còn mình lấy là `0` nên hai bên sẽ chênh nhau một thứ tự, không quan trọng.
> Bài toán Fibonacci này đã khép lại series 5 bài một tháng tự bơi Assembly của mình, mong rằng trong tương lai mình sẽ có cơ hội học được nhiều kiến thức bổ ích hơn nữa. Hi vọng bài viết này hữu ích với các bạn. Dear!!!