Fibonacci là gì?

Dãy Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

Mỗi số là tổng của hai số trước đó. Chúng ta sẽ tính fib(14) = 377.

Cấu trúc chương trình Assembly

Mẫu cơ bản

section .data
	; Khai báo dữ liệu ở đây
	result dd 0

section .text
	; Mã lệnh ở đây
	hlt  ; Luôn kết thúc bằng halt

Cài đặt Fibonacci (Lặp)

Tạo file fib14.asm:

section .data
	result dd 0

section .text
	mov ecx, 14      ; n = 14 (bộ đếm)
	mov eax, 0       ; a = 0 (số trước)
	mov ebx, 1       ; b = 1 (số hiện tại)
	
loop:
	cmp ecx, 0       ; nếu bộ đếm == 0
	je done          ; nhảy đến done
	mov edx, eax     ; temp = a
	mov eax, ebx     ; a = b
	add ebx, edx     ; b = b + temp
	sub ecx, 1       ; bộ đếm--
	jmp loop         ; lặp lại
	
done:
	mov [result], eax  ; lưu kết quả
	hlt                ; dừng chương trình

Cách hoạt động

Phân tích thuật toán

1. Khởi tạo:

   • ecx = 14 (bộ đếm vòng lặp)
   • eax = 0 (số Fibonacci trước)
   • ebx = 1 (số Fibonacci hiện tại)

2. Vòng lặp (14 lần lặp):

   • Lưu eax vào edx (tạm)
   • Chuyển ebx sang eax (dịch số hiện tại thành số trước)
   • Cộng edx vào ebx (tính số Fibonacci tiếp theo)
   • Giảm bộ đếm
   • Lặp lại cho đến khi bộ đếm = 0

3. Kết quả: eax chứa fib(14) = 377

Bảng lặp

Chạy chương trình

Xây dựng trình mô phỏng

cd CPU/build
cmake ..
make

Thực thi

./app -f ../fib14.asm -s 100000

Tham số:

• -f : File assembly đầu vào
• -s : Tốc độ (lệnh mỗi phút)

Xác minh kết quả

Đầu ra hiển thị trạng thái CPU bao gồm phần dữ liệu. Tìm:

Data
e8 03 00 00 ...

Khoan, sai rồi! Hãy kiểm tra hex:

• 79 01 00 00 ở định dạng little-endian
• Bytes: 0x79, 0x01, 0x00, 0x00
• Giá trị: 0x0179 = 377 thập phân ✓

Hiểu về Little-Endian

x86-64 sử dụng thứ tự byte little-endian (byte ít quan trọng nhất đứng trước):

Bộ nhớ: [79] [01] [00] [00]
LSB MSB

Giá trị = 0x00000179 = 377

Kiểm tra các giá trị khác

fib(10) = 55

mov ecx, 10
; ... phần còn lại

Kỳ vọng: 37 00 00 00 (0x37 = 55)

fib(20) = 6765

mov ecx, 20
; ... phần còn lại

Kỳ vọng: 6d 1a 00 00 (0x1a6d = 6765)

Lỗi thường gặp

1. Quên hlt

mov [result], eax
; Thiếu hlt - gây lỗi segmentation fault!

Sửa: Luôn kết thúc bằng hlt

2. Điều kiện vòng lặp sai

cmp ecx, 1    ; Sai! Dừng ở 1
je done

Sửa: Dùng cmp ecx, 0

3. Nhầm lẫn thanh ghi

mov eax, ebx
add eax, edx  ; Sai! Sửa đổi eax trước khi dùng
mov ebx, eax

Sửa: Dùng thanh ghi tạm đúng cách

Cài đặt đệ quy

Dành cho người dùng nâng cao, đây là phiên bản đệ quy:

section .data
	result dd 0

section .text
	push 14
	call fib
	add esp, 4
	mov [result], eax
	hlt

fib:
	push ebp
	mov ebp, esp
	
	mov eax, [ebp + 8]  ; lấy n
	cmp eax, 1
	jle base_case
	
	; fib(n-1)
	sub eax, 1
	push eax
	call fib
	add esp, 4
	mov ebx, eax
	
	; fib(n-2)
	mov eax, [ebp + 8]
	sub eax, 2
	push eax
	call fib
	add esp, 4
	
	add eax, ebx
	jmp end
	
base_case:
	mov eax, [ebp + 8]
	
end:
	pop ebp
	ret

Lưu ý: Phiên bản đệ quy chậm hơn (độ phức tạp thời gian mũ).

Mẹo gỡ lỗi

1. Kiểm tra với giá trị nhỏ

Bắt đầu với fib(5) = 5 để xác minh logic:

./app -f fib5.asm -s 10000

Kỳ vọng: 05 00 00 00

2. Dùng chế độ tương tác

./app -f fib14.asm -i

Thực thi từng lệnh một.

3. Kiểm tra thanh ghi

Theo dõi giá trị thanh ghi trong TUI:

• ecx: Bộ đếm vòng lặp (phải giảm)
• eax: Số Fibonacci trước
• ebx: Số Fibonacci hiện tại

Hiệu năng

Fibonacci lặp là O(n):

• fib(14): ~14 lần lặp
• fib(100): ~100 lần lặp

Đệ quy là O(2^n):

• fib(14): ~2,584 lời gọi
• fib(20): ~21,891 lời gọi (rất chậm!)

Đố vui

1. Sửa đổi để tính fib(20)
2. Thêm vòng lặp để tính 10 số Fibonacci đầu tiên
3. Cài đặt chỉ dùng 2 thanh ghi (thử thách!)
4. Tạo phiên bản lưu kết quả vào mảng

Tham khảo

Thanh ghi sử dụng

• eax: Accumulator (giá trị trước)
• ebx: Base (giá trị hiện tại)
• ecx: Counter (số lần lặp)
• edx: Data (lưu trữ tạm)

Lệnh sử dụng

• mov: Di chuyển dữ liệu
• add: Cộng
• sub: Trừ
• cmp: So sánh
• je: Nhảy nếu bằng
• jmp: Nhảy vô điều kiện
• hlt: Dừng thực thi

Kết quả kỳ vọng

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(10) = 55
fib(14) = 377
fib(20) = 6765

Xác minh

Chuyển đổi hex sang thập phân:

python3 -c "print(0x0179)"  # Kết quả: 377

Hoặc dùng máy tính:

• 0x179 = 1×256 + 7×16 + 9×1 = 256 + 112 + 9 = 377 ✓