Fibonacci Sequence¶

This example calculates the 10th Fibonacci number using an iterative approach.

Overview¶

Difficulty: Beginner

Concepts: Loops, register arithmetic, conditional branching

Output: R17 contains F(10) = 55

The Program¶

; Fibonacci Sequence Calculator
; Calculates the 10th Fibonacci number (F(10) = 55)
; F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
;
; Results stored in registers:
; R16 and R17 hold the two most recent Fibonacci numbers

    ldi r16, 0          ; F(0) = 0
    ldi r17, 1          ; F(1) = 1
    ldi r18, 9          ; Counter: 9 more iterations to reach F(10)

loop:
    add r16, r17        ; F(n) = F(n-1) + F(n-2)
    mov r19, r16        ; Save result temporarily
    mov r16, r17        ; Shift: previous = current
    mov r17, r19        ; Shift: current = new result
    dec r18             ; Decrement counter
    brne loop           ; Continue if counter != 0

done:
    jmp done            ; Infinite loop at end

Algorithm Explanation¶

The Fibonacci sequence is defined as:

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

This program uses an iterative approach with three registers:

R16: Previous Fibonacci number (F(n-1))
R17: Current Fibonacci number (F(n))
R18: Counter (remaining iterations)

Step-by-Step Walkthrough¶

Initialization (Lines 8-10)¶

ldi r16, 0          ; F(0) = 0
ldi r17, 1          ; F(1) = 1
ldi r18, 9          ; Counter: 9 more iterations

We start with F(0) = 0 and F(1) = 1. Since we want F(10), we need 9 more iterations (F(2) through F(10)).

Main Loop (Lines 12-18)¶

loop:
    add r16, r17        ; F(n) = F(n-1) + F(n-2)
    mov r19, r16        ; Save result temporarily
    mov r16, r17        ; Shift: previous = current
    mov r17, r19        ; Shift: current = new result
    dec r18             ; Decrement counter
    brne loop           ; Continue if counter != 0

Each iteration:

Add: Compute next Fibonacci number (R16 + R17)
Save: Store result in temporary register R19
Shift: Move R17 to R16 (previous ← current)
Update: Move R19 to R17 (current ← new result)
Decrement: Decrease counter
Branch: Loop if counter ≠ 0

Execution Trace¶

Here’s how the registers evolve:

Fibonacci Calculation¶
Iter	R16 (prev)	R17 (curr)	R18 (count)	Calculation
Init	0	1	9	F(0), F(1)
1	1	1	8	F(2) = 0 + 1 = 1
2	1	2	7	F(3) = 1 + 1 = 2
3	2	3	6	F(4) = 1 + 2 = 3
4	3	5	5	F(5) = 2 + 3 = 5
5	5	8	4	F(6) = 3 + 5 = 8
6	8	13	3	F(7) = 5 + 8 = 13
7	13	21	2	F(8) = 8 + 13 = 21
8	21	34	1	F(9) = 13 + 21 = 34
9	34	55	0	F(10) = 21 + 34 = 55

Running the Example¶

Interactive Debugger¶

tiny8 examples/fibonacci.asm

Step through with j and watch registers R16, R17, and R18 evolve.

Animation¶

tiny8 examples/fibonacci.asm -m ani -o fibonacci.gif

Visualize the register changes over time.

Python API¶

from tiny8 import CPU, assemble_file

cpu = CPU()
cpu.load_program(assemble_file("examples/fibonacci.asm"))
cpu.run(max_steps=100)

print(f"F(10) = {cpu.read_reg(17)}")  # Output: 55

Key Concepts¶

Loop Structure¶

The loop pattern is common in assembly:

ldi r18, N          ; Initialize counter
loop:
    ; ... loop body ...
    dec r18         ; Decrement counter
    brne loop       ; Branch if not equal to zero

Register Shifting¶

Moving values between registers for state management:

mov r19, r16        ; Temporary save
mov r16, r17        ; Shift values
mov r17, r19        ; Update with new value

This “register rotation” is a fundamental technique in assembly programming.

Exercises¶

Modify the counter: Calculate F(15) instead of F(10)
Different starting values: Try F(0) = 1, F(1) = 1 (alternative definition)
Store in memory: Save each Fibonacci number to memory
Detect overflow: Check when the result exceeds 255

Solutions¶

F(15) modification:

ldi r18, 14         ; 14 iterations for F(15)

Note: F(15) = 610, which exceeds 8-bit range (wraps to 98).

Store in memory:

ldi r20, 0x60       ; Memory base address
loop:
    add r16, r17
    sts r20, r17    ; Store current Fibonacci number
    inc r20         ; Advance memory pointer
    ; ... rest of loop ...