ARM Assembly Program to Calculate Fibonacci Numbers

An ARM assembly program to calculate the Fibonacci number uses registers to store previous two numbers and a loop with ADD and SUBS instructions; for example, the code initializes r0=0, r1=1, and loops to compute up to the nth Fibonacci number.

Examples

Inputn=0

Output0

Inputn=5

Output5

Inputn=10

Output55

How to Think About It

To write a Fibonacci program in ARM assembly, start by storing the first two Fibonacci numbers in registers. Use a loop to add the last two numbers to get the next one, updating registers each iteration. Continue until you reach the desired position n, then output the result.

Algorithm

1

Load the input number n.

2

Initialize two registers with 0 and 1 for the first two Fibonacci numbers.

3

If n is 0 or 1, return the corresponding Fibonacci number immediately.

4

Use a loop to calculate the next Fibonacci number by adding the previous two.

5

Update registers to hold the last two Fibonacci numbers.

6

Repeat until the nth Fibonacci number is calculated.

7

Return the result.

Code

arm_architecture

    .section .data
input:  .word 10
output: .word 0

    .section .text
    .global _start

_start:
    LDR r2, =input      @ Load address of input
    LDR r3, [r2]       @ Load n
    MOV r0, #0         @ fib0 = 0
    MOV r1, #1         @ fib1 = 1
    CMP r3, #0
    BEQ done           @ if n==0, result is 0
    CMP r3, #1
    BEQ done           @ if n==1, result is 1
    SUBS r3, r3, #1    @ n = n - 1
loop:
    ADD r4, r0, r1     @ fib_next = fib0 + fib1
    MOV r0, r1         @ fib0 = fib1
    MOV r1, r4         @ fib1 = fib_next
    SUBS r3, r3, #1    @ n = n - 1
    BNE loop

done:
    LDR r2, =output
    STR r1, [r2]       @ Store result

    MOV r7, #1         @ syscall: exit
    MOV r0, #0         @ status 0
    SVC #0             @ make syscall

Output

55

Dry Run

Let's trace n=5 through the code to see how Fibonacci numbers are calculated.

1

Initialize registers

r0=0 (fib0), r1=1 (fib1), r3=5 (n)

2

Check if n is 0 or 1

n=5, so continue loop

3

Start loop iteration 1

r4 = r0 + r1 = 0 + 1 = 1; r0 = 1; r1 = 1; n = 4

4

Loop iteration 2

r4 = 1 + 1 = 2; r0 = 1; r1 = 2; n = 3

5

Loop iteration 3

r4 = 1 + 2 = 3; r0 = 2; r1 = 3; n = 2

6

Loop iteration 4

r4 = 2 + 3 = 5; r0 = 3; r1 = 5; n = 1

7

Loop iteration 5

r4 = 3 + 5 = 8; r0 = 5; r1 = 8; n = 0 (exit loop)

8

Store result

Result stored in output = 8

Iteration	fib0 (r0)	fib1 (r1)	fib_next (r4)	n (r3)
Start	0	1	-	5
1	1	1	1	4
2	1	2	2	3
3	2	3	3	2
4	3	5	5	1
5	5	8	8	0

Why This Works

Step 1: Initialize first two Fibonacci numbers

Registers r0 and r1 hold the first two Fibonacci numbers 0 and 1, which are the base cases.

Step 2: Use loop to calculate next numbers

Each loop iteration adds the last two Fibonacci numbers to get the next one, updating registers accordingly.

Step 3: Loop until nth number

The loop runs n-1 times because the first two numbers are already known, ensuring the nth Fibonacci number is computed.

Step 4: Store and output result

After the loop, the result is stored in memory and the program exits cleanly.

Alternative Approaches

Recursive approach

arm_architecture

    .section .text
    .global fib
fib:
    CMP r0, #1
    BLE end
    PUSH {lr}
    SUB r0, r0, #1
    BL fib
    MOV r1, r0
    POP {lr}
    SUB r0, r0, #2
    BL fib
    ADD r0, r0, r1
end:
    BX lr

Uses recursion which is elegant but inefficient and uses more stack memory.

Using memory array

arm_architecture

    .section .bss
fib_array: .space 40
    .section .text
    .global _start
_start:
    MOV r4, #0
    MOV r5, #1
    MOV r6, #10
    STR r4, [fib_array]
    STR r5, [fib_array, #4]
loop:
    SUBS r6, r6, #1
    BEQ done
    LDR r0, [fib_array, r6, LSL #2]
    LDR r1, [fib_array, r6, LSL #2, #-4]
    ADD r2, r0, r1
    STR r2, [fib_array, r6, LSL #2, #-8]
    B loop
done:
    MOV r7, #1
    MOV r0, #0
    SVC #0

Stores all Fibonacci numbers in memory, useful for accessing any previous number but uses more memory.

Complexity: O(n) time, O(1) space

Time Complexity

The program runs a single loop n-1 times, so the time complexity is linear O(n).

Space Complexity

Only a few registers are used to store intermediate values, so space complexity is constant O(1).

Which Approach is Fastest?

The iterative register-based approach is fastest and most memory efficient compared to recursion or memory array methods.

Approach	Time	Space	Best For
Iterative with registers	O(n)	O(1)	Fast, low memory
Recursive	O(2^n)	O(n)	Simple code but slow and stack-heavy
Memory array	O(n)	O(n)	Access to all Fibonacci numbers