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

No comments:

Post a Comment