Friday, 28 June 2013

The Fibonacci sequence

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

```.syntax unified

.equ maxfib,4000000

previous .req r4
current  .req r5
next     .req r6
sum      .req r7
max      .req r8
tmp      .req r9

.section .rodata
.align 2
fibstring:
.asciz "fib is %d\n"
sumstring:
.asciz "%d\n"

.text
.align 2
.global main
.type main, %function
main:
stmfd sp!, {r4-r9, lr}
ldr max,   =maxfib
mov previous, 1
mov current, 1
mov sum, 0

loop:
cmp current, max
bgt last

add next, current, previous

movs tmp, current, lsr 1      @ set carry flag from lsr - for the odd-valued terms
@ we discard the result of the movs and are only interested
@ in the side effect of the lsr which pushes the lower bit
@ of current (1 for odd; 0 for even) into the carry flag
@ movs will update the status register (c.f. mov which will not)
addcc sum, sum, current       @ we add current to the sum ONLY when cc (carry clear) is true
@ these are even-valued fibonacci terms

mov previous, current
mov current, next
b loop

last:
mov r1, sum
ldr r0, =sumstring            @ store address of start of string to r0
bl printf

mov r0, 0
ldmfd sp!, {r4-r9, pc}
mov r7, 1                     @ set r7 to 1 - the syscall for exit
swi 0                         @ then invoke the syscall from linux
```