Find product of digits

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

.syntax unified

.equ limit,10000
.equ outer, 996
.equ inner, 5 

.align 4

address  .req r4
thisbyte .req r5
icounter .req r6
ocounter .req r7
maxv     .req r8
tmp      .req r9

.section .data
buffer:
.byte 7, 3, 1, 6, 7, 1, 7, 6, 5, 3, 1, 3, 3, 0, 6, 2, 4, 9, 1, 9, 2, 2
.byte 5, 1, 1, 9, 6, 7, 4, 4, 2, 6, 5, 7, 4, 7, 4, 2, 3, 5, 5, 3, 4, 9, 1, 9
.byte 4, 9, 3, 4, 9, 6, 9, 8, 3, 5, 2, 0, 3, 1, 2, 7, 7, 4, 5, 0, 6, 3, 2, 6
.byte 2, 3, 9, 5, 7, 8, 3, 1, 8, 0, 1, 6, 9, 8, 4, 8, 0, 1, 8, 6, 9, 4, 7, 8
.byte 8, 5, 1, 8, 4, 3, 8, 5, 8, 6, 1, 5, 6, 0, 7, 8, 9, 1, 1, 2, 9, 4, 9, 4
.byte 9, 5, 4, 5, 9, 5, 0, 1, 7, 3, 7, 9, 5, 8, 3, 3, 1, 9, 5, 2, 8, 5, 3, 2
.byte 0, 8, 8, 0, 5, 5, 1, 1, 1, 2, 5, 4, 0, 6, 9, 8, 7, 4, 7, 1, 5, 8, 5, 2
.byte 3, 8, 6, 3, 0, 5, 0, 7, 1, 5, 6, 9, 3, 2, 9, 0, 9, 6, 3, 2, 9, 5, 2, 2
.byte 7, 4, 4, 3, 0, 4, 3, 5, 5, 7, 6, 6, 8, 9, 6, 6, 4, 8, 9, 5, 0, 4, 4, 5
.byte 2, 4, 4, 5, 2, 3, 1, 6, 1, 7, 3, 1, 8, 5, 6, 4, 0, 3, 0, 9, 8, 7, 1, 1
.byte 1, 2, 1, 7, 2, 2, 3, 8, 3, 1, 1, 3, 6, 2, 2, 2, 9, 8, 9, 3, 4, 2, 3, 3
.byte 8, 0, 3, 0, 8, 1, 3, 5, 3, 3, 6, 2, 7, 6, 6, 1, 4, 2, 8, 2, 8, 0, 6, 4
.byte 4, 4, 4, 8, 6, 6, 4, 5, 2, 3, 8, 7, 4, 9, 3, 0, 3, 5, 8, 9, 0, 7, 2, 9
.byte 6, 2, 9, 0, 4, 9, 1, 5, 6, 0, 4, 4, 0, 7, 7, 2, 3, 9, 0, 7, 1, 3, 8, 1
.byte 0, 5, 1, 5, 8, 5, 9, 3, 0, 7, 9, 6, 0, 8, 6, 6, 7, 0, 1, 7, 2, 4, 2, 7
.byte 1, 2, 1, 8, 8, 3, 9, 9, 8, 7, 9, 7, 9, 0, 8, 7, 9, 2, 2, 7, 4, 9, 2, 1
.byte 9, 0, 1, 6, 9, 9, 7, 2, 0, 8, 8, 8, 0, 9, 3, 7, 7, 6, 6, 5, 7, 2, 7, 3
.byte 3, 3, 0, 0, 1, 0, 5, 3, 3, 6, 7, 8, 8, 1, 2, 2, 0, 2, 3, 5, 4, 2, 1, 8
.byte 0, 9, 7, 5, 1, 2, 5, 4, 5, 4, 0, 5, 9, 4, 7, 5, 2, 2, 4, 3, 5, 2, 5, 8
.byte 4, 9, 0, 7, 7, 1, 1, 6, 7, 0, 5, 5, 6, 0, 1, 3, 6, 0, 4, 8, 3, 9, 5, 8
.byte 6, 4, 4, 6, 7, 0, 6, 3, 2, 4, 4, 1, 5, 7, 2, 2, 1, 5, 5, 3, 9, 7, 5, 3
.byte 6, 9, 7, 8, 1, 7, 9, 7, 7, 8, 4, 6, 1, 7, 4, 0, 6, 4, 9, 5, 5, 1, 4, 9
.byte 2, 9, 0, 8, 6, 2, 5, 6, 9, 3, 2, 1, 9, 7, 8, 4, 6, 8, 6, 2, 2, 4, 8, 2
.byte 8, 3, 9, 7, 2, 2, 4, 1, 3, 7, 5, 6, 5, 7, 0, 5, 6, 0, 5, 7, 4, 9, 0, 2
.byte 6, 1, 4, 0, 7, 9, 7, 2, 9, 6, 8, 6, 5, 2, 4, 1, 4, 5, 3, 5, 1, 0, 0, 4
.byte 7, 4, 8, 2, 1, 6, 6, 3, 7, 0, 4, 8, 4, 4, 0, 3, 1, 9, 9, 8, 9, 0, 0, 0
.byte 8, 8, 9, 5, 2, 4, 3, 4, 5, 0, 6, 5, 8, 5, 4, 1, 2, 2, 7, 5, 8, 8, 6, 6
.byte 6, 8, 8, 1, 1, 6, 4, 2, 7, 1, 7, 1, 4, 7, 9, 9, 2, 4, 4, 4, 2, 9, 2, 8
.byte 2, 3, 0, 8, 6, 3, 4, 6, 5, 6, 7, 4, 8, 1, 3, 9, 1, 9, 1, 2, 3, 1, 6, 2
.byte 8, 2, 4, 5, 8, 6, 1, 7, 8, 6, 6, 4, 5, 8, 3, 5, 9, 1, 2, 4, 5, 6, 6, 5
.byte 2, 9, 4, 7, 6, 5, 4, 5, 6, 8, 2, 8, 4, 8, 9, 1, 2, 8, 8, 3, 1, 4, 2, 6
.byte 0, 7, 6, 9, 0, 0, 4, 2, 2, 4, 2, 1, 9, 0, 2, 2, 6, 7, 1, 0, 5, 5, 6, 2
.byte 6, 3, 2, 1, 1, 1, 1, 1, 0, 9, 3, 7, 0, 5, 4, 4, 2, 1, 7, 5, 0, 6, 9, 4
.byte 1, 6, 5, 8, 9, 6, 0, 4, 0, 8, 0, 7, 1, 9, 8, 4, 0, 3, 8, 5, 0, 9, 6, 2
.byte 4, 5, 5, 4, 4, 4, 3, 6, 2, 9, 8, 1, 2, 3, 0, 9, 8, 7, 8, 7, 9, 9, 2, 7
.byte 2, 4, 4, 2, 8, 4, 9, 0, 9, 1, 8, 8, 8, 4, 5, 8, 0, 1, 5, 6, 1, 6, 6, 0
.byte 9, 7, 9, 1, 9, 1, 3, 3, 8, 7, 5, 4, 9, 9, 2, 0, 0, 5, 2, 4, 0, 6, 3, 6
.byte 8, 9, 9, 1, 2, 5, 6, 0, 7, 1, 7, 6, 0, 6, 0, 5, 8, 8, 6, 1, 1, 6, 4, 6
.byte 7, 1, 0, 9, 4, 0, 5, 0, 7, 7, 5, 4, 1, 0, 0, 2, 2, 5, 6, 9, 8, 3, 1, 5
.byte 5, 2, 0, 0, 0, 5, 5, 9, 3, 5, 7, 2, 9, 7, 2, 5, 7, 1, 6, 3, 6, 2, 6, 9
.byte 5, 6, 1, 8, 8, 2, 6, 7, 0, 4, 2, 8, 2, 5, 2, 4, 8, 3, 6, 0, 0, 8, 2, 3
.byte 2, 5, 7, 5, 3, 0, 4, 2, 0, 7, 5, 2, 9, 6, 3, 4, 5, 0

.section .rodata
.align  2
resstring:
        .asciz "%d\n"
.text
.align  2
.global main
.type   main, %function
main:
 stmfd   sp!, {r4-r9, lr}
 ldr address, =buffer
 ldr ocounter, =outer
outer_start:
 ldr icounter, =inner
 mov tmp, #1
inner_start:
 ldrb thisbyte, [address], 1
 mul tmp, tmp, thisbyte
 subs icounter, icounter, 1
 bne inner_start
 cmp maxv, tmp
 movlt maxv, tmp            @ overwrite maxv with tmp if tmp is bigger 
 sub address, address, 4
 subs ocounter, ocounter, 1
 bne outer_start

printme:
 mov     r1, maxv
 ldr     r0, =resstring     @ 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

Finding prime numbers

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

.syntax unified

.equ limit,10000
.equ limit4,40000

.align 4

number     .req r4
count      .req r5
numprimes  .req r6
primes_ptr .req r7

.section .bss
.lcomm primes_vector,limit4 # sufficient for 10000 32-bit ints

.section .rodata
 .align 2
resstring:
 .asciz "%d\n"
.text
 .align 2
 .global main
 .type main, %function
main:
 stmfd sp!, {r4-r7, lr}

 ldr     primes_ptr, =primes_vector
 mov     numprimes, 1
 mov     number, 2
 str     number, [primes_ptr]

 ldr count, =limit
 mov number, 3                                 @ 2 is the first prime
loop:
 mov     r0, number
 ldr     r1, =primes_vector
 mov     r2, numprimes
 bl      prime_vector
 teq     r0, 1
 bne     nexti
 str     number, [primes_ptr, numprimes, lsl 2]
 add     numprimes, numprimes, 1
 subs count, count, 1
 beq printme
nexti:
 add number, number, 2
 b loop
 
printme:
 mov r1, number
 ldr r0, =resstring                            @ store address of start of string to r0
 bl printf

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

prime_vector.s
.syntax unified
.equ word, 4

# this subroutine returns 1 if the passed number is prime; 0 if not
#
# inputs
#   r0 - integer to test
#   r1 - pointer to vector of prime integers smaller than r0
#   r2 - length of vector passed in r1
#
# outputs
#   r0 - prime boolean

number   .req r4
vptr     .req r5
tmp      .req r6
squared  .req r7
vsize    .req r8

.global prime_vector
.type prime_vector, %function
.text
.align 2

prime_vector:
 stmfd sp!, {r4-r8, lr}
 mov number, r0
 mov vptr, r1
 mov vsize, r2
nexti:
 ldr tmp, [vptr], word
 mul squared, tmp, tmp
 cmp squared, number    @ check if vector element squared is greater than test number
 movgt r0, 1              @ if so test numer is prime so leave
 bgt last
 mov r0, number
 mov r1, tmp
 bl divide             @ divide number by vector element - if no remainder
 teq r1, 0              @ it is not prime so leave
 moveq r0, 0
 beq last
 subs vsize, vsize, 1    @ check next element
 bgt nexti
 mov r0, 0
last:
 ldmfd sp!, {r4-r8, pc}

divide.s

.syntax unified
# divide takes value in r0, divisor in r1 and returns dividend in r0 and modulus in r1 
 .global divide
 .type divide, %function
divide:
        stmfd   sp!, {lr}
# see http://infocenter.arm.com/help/topic/com.arm.doc.ihi0043d/IHI0043D_rtabi.pdf
 bl __aeabi_uidivmod
 ldmfd   sp!, {pc}

Sum squares and square sums

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

.syntax unified

.equ limit,100

number .req r4
sumsq .req r5
sqsum .req r6
tmp .req r7

.section .rodata
 .align 2
string:
 .asciz "%d\n"
.text
 .align 2
 .global main
 .type main, %function
main:
 stmfd sp!, {r4-r7, lr}
 mov sqsum, 0
 mov sumsq, 0
 ldr number, =limit
loop:
 mul tmp, number, number
 add sqsum, sqsum, tmp
# decrement number and loop or exit
 subs number, number, 1
 beq end_loop
 b loop
end_loop:
 ldr number, =limit
 add number, number, 1
 ldr sumsq, =limit
 mul sumsq, sumsq, number
 lsr sumsq, sumsq, 1
 mul sumsq, sumsq, sumsq
last:
 sub tmp, sumsq, sqsum 
 mov r1, tmp
 ldr r0, =string         @ store address of start of string to r0
 bl printf

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

Divisibility

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

.syntax unified

.equ limit,20

.align 4

@ algorithm
@ initialise try_products to 1
@ foreach number > 1 and <= limit
@ test if it is prime
@ if try_products is set, then multiply the number by itself 
@ while it does not exceed limit, then multiply the total by
@ this product. if the number squared exceeds the limit, then 
@ set try_product to 0.
@ if try_products is 0 and the number is prime, then multiply
@ the total by number.

try_product .req r4
number      .req r5
last        .req r6
total       .req r7
tmp         .req r8

.section .rodata
 .align 2
resstring:
 .asciz "%d\n"
.text
 .align 2
 .global main
 .type main, %function
main:
 stmfd sp!, {r4-r8, lr}

 mov total, 1
 mov try_product, 1
 mov number, 2
loop:
 mov r0, number
 bl isprime20
 cmp r0, 1
 bne nexti
 
 cmp try_product, 1
 bne no_product
 mul tmp, number, number
 cmp tmp, limit
 ble prod_start
 mov try_product, 0
 b no_product
prod_start:
 mov tmp, number
 mov last, tmp
prod_loop:
 cmp tmp, limit
 bgt last_mul
 mov last, tmp
 mul tmp, tmp, number
 b prod_loop
last_mul:
 mul total, total, last
no_product:
 cmp try_product, 0
 bne nexti
 mul total, total, number
nexti:
 cmp number, limit
 beq printme
 add number, number, 1
 b loop
 
printme:
 mov r1, total
 ldr r0, =resstring        @ store address of start of string to r0
 bl printf

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

# this subroutine returns 1 if the passed number (<= 20) is prime; 0 if not
#
# inputs
#   r0 - integer to test
#
# outputs
#   r0 - prime boolean

.global isprime20
.type isprime20, %function
.text
.align 2

isprime20:
 stmfd sp!, {lr}
 mov r1, r0
 ands r2, r1, 1
 bne odd
 mov r0, 0
 cmp r1, 2                @ 2 is the only prime even r1
 bne last
 mov r0, 1
 b last
odd:
 mov r0, 1
 cmp r1, 9                @ 9 and 15 are the only non-prime 
 bne test15               @ odd numbers less than 20   
 mov r0, 0
 b last
test15:
 cmp r1, 15
 bne last
 mov r0, 0
last:
 ldmfd sp!, {pc}

Palindromic numbers

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

.syntax unified

.equ max3,999
.equ min3,100
.equ maxdigits,6

i       .req r4
j       .req r5
product .req r6
maxp    .req r7
mini    .req r8
minj    .req r9
maxj    .req r10

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

.text
 .align 2
 .global main
 .type main, %function
main:
 stmfd sp!, {r4-r10, lr}
 ldr i, =max3
 ldr mini, =min3
 ldr maxj, =max3
 ldr minj, =min3
iloop:
 mov j, maxj
jloop:
 mul product, i, j

 mov r0, product
 bl is_palindromic
 cmp r0, #1
 bne next
 cmp product, maxp
 ble next
 mov maxp, product
 mov r0, product
 bl divide_by_10         @ divides r0 by 10 
 bl divide_by_10         @ so 3 consecutive calls
 bl divide_by_10         @ will divide by 1000
 mov minj, r0
 mov minj, r0

next:
 subs j, j, 1
 cmp j, minj
 bgt jloop

 subs i, i, 1
 mov maxj, i
 cmp i, mini
 bgt iloop

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

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

A division of the found product by 1000 to reset the minima is an optimisation to speed termination.

We divide by 10 three times in succession - we could write a routine to divide by 1000, but one to divide by 10 is much more useful.

ispalindromic.s
.syntax unified

.equ datum_size, 1
.equ digits, 6

# this subroutine returns 1 if the passed 6-digit number is palindromic; 0 if not
# the number is a product of 2 3-digit numbers so we assume the product has 6 digits
#
# inputs
#   r0 - integer to test
#
# outputs
#   r0 - palindromic boolean
#
# local
#
 left           .req r4
 right          .req r5
 counter        .req r6
 buffer_address .req r7
 running        .req r8
 tmp            .req r9
#  
.section .bss
   .lcomm buffer, 6                  @ use digits here?
#
.global is_palindromic
.type is_palindromic, %function
.global get_digits
.type get_digits, %function
.text
.align 2
#
is_palindromic:
 stmfd sp!, {r4-r9, lr}
 bl get_digits
 mov counter, 3                      @ digits >> 1
 ldr buffer_address, =buffer
ip_last:                             @ the next few lines are the nub of the problem
 sub left, buffer_address, counter   @ on the first pass we compare x[0] and x[5]
 ldrb tmp, [left, 3]                 @ if they are equal we compare x[1] and x[4]
 add right, buffer_address, counter  @ if they are equal we compare x[2] and x[3]
 ldrb running, [right, 2]
 teq tmp, running
 bne no                              @ mismatch between tested digits
 subs counter, counter, 1
 bgt ip_last                         @ test next pair for equality
 mov r0, 1
 b  last
no:
 mov r0, 0
last:
 ldmfd sp!, {r4-r9, pc}
#
get_digits:                             @ this routine writes a number into a string
 stmfd sp!, {r7-r8, lr}
 ldr running, =digits
 ldr buffer_address, =buffer
gd_loop:
 subs running, running, 1
 bl divide_by_10_remainder
 strb r1, [buffer_address], #datum_size
 bgt gd_loop

gd_last:
 ldmfd sp!, {r7-r8, pc}

divide_by_10.s
.syntax unified

# this subroutine divides the passed number by 10 and
# returns the dividend and remainder
# 
# The const -0x33333333 is 0xccccccd (2s complement)
# 0xcccccccc is 12/15th (0.8) of 0xffffffff and we use this as
# a multiplier, then shift right by 3 bits (divide by 8) to 
# effect a multiplication by 0.1
#
# We multiply this number by 10 (multiply by 4, add 1 then multiply by 2)
# and subtract from the original number to give the remainder on division
# by 10.
#
# inputs
#   r0 - integer to divide
#
# outputs
#   r0 - the dividend 
#   r1 - the remainder 

.equ const,-0x33333333
#.equ const,0xcccccccd
.text
.align 2
.global divide_by_10_remainder
.type divide_by_10_remainder, %function
divide_by_10_remainder:
 stmfd sp!, {lr}
 cmp r0, 10
 blt rsmall
 ldr r1, =const
 umull r2, r3, r1, r0
 mov r2, r3, lsr #3              @ r2 = r3 / 8 == r0 / 10
 mov r3, r2                      @ r3 = r2
 mov r3, r3, asl #2              @ r3 = 4 * r3
 add r3, r3, r2                  @ r3 = r3 + r2
 mov r3, r3, asl #1              @ r3 = 2 * r3 
 rsb r3, r3, r0                  @ r3 = r0 - r3 = r0 - 10*int(r0/10)
 mov r1, r3                      @ the remainder
 mov r0, r2                      @ the dividend
 b rlast
rsmall:
 mov r1, r0
 mov r0, 0
rlast:
 ldmfd sp!, {pc}


# this subroutine divides the passed number by 10
# returns the dividend
# 
# The const -0x33333333 is 0xccccccd (2s complement)
# 0xcccccccc is 12/15th (0.8) of 0xffffffff and we use this as
# a multiplier, then shift right by 3 bits (divide by 8) to 
# effect a multiplication by 0.1
#
# We multiply this number by 10 (multiply by 4, add 1 then multiply by 2)
#
# inputs
#   r0 - integer to divide
#
# outputs
#   r0 - the dividend 

.align 2
.global divide_by_10
.type divide_by_10, %function
divide_by_10:
 stmfd sp!, {lr}
 cmp r0, 10
 blt small
 ldr r1, =const
 umull r2, r3, r1, r0
 mov r2, r3, lsr #3              @ r2 = r3 / 8 == r0 / 10
 mov r0, r2                      @ the dividend
 b last
small:
 mov r0, 0
last:
 ldmfd sp!, {pc}

Prime factors

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

.syntax unified

@ 600851475143 is 8BE589EAC7 in hex

.equ numhi,139        @ 0x8b
.equ numlo,3851020999 @ 0xe589eac7

num_hi  .req r4
num_lo  .req r5
maxdiv  .req r6
n       .req r7

.section .rodata
 .align 2
resstring:
 .asciz "%d\n"
.text
 .align 2
 .global main
 .type main, %function
main:
 stmfd sp!, {r4-r7, lr}

 mov maxdiv, 0
 mov n, 1
 ldr num_lo, =numlo
 ldr num_hi, =numhi
loop:
 add n, n, 2           @ start at 3 and increment by 2
loop1:
 mov r0, num_lo
 mov r1, num_hi
 mov r2, n
 mov r3, 0
 bl  long_divide
 teq r2, 0
 bne loop
 teq r3, 0
 bne loop
 mov num_lo, r0         @ only get here when we have no remainder
 mov num_hi, r1         @ save the divisor as the new number
 mov r0, n
 bl isprime
 teq r0, 1
 bne loop               @ increment n if n is non-prime
 cmp maxdiv, n
 movlt maxdiv, n        @ save n as the largest divisor if it is larger
 teq num_lo, 1          @ we know it has prime factors
 beq printme
 b loop1
printme:
 mov r1, maxdiv
 ldr r0, =resstring     @ store address of start of string to r0
 bl printf

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

The ARM is a RISC microprocessor and does not provide a divide command in the instruction set. We use a division routine from libgcc.

Using the -S option to gcc when a c file is compiled will generate an assembly language file which can be read for enlightenment.

isprime.s
.syntax unified

# this subroutine returns 1 if the passed number is prime; 0 if not

# inputs
#   r0 - integer to test

# outputs
#   r0 - prime boolean

number   .req r4
divisor  .req r5
tmp      .req r6

.global isprime
.type isprime, %function
.text
.align 2

isprime:
 stmfd sp!, {r4-r6, lr}
 mov number, r0
 ands tmp, number, 1
 bne odd
 mov r0, 0
 cmp number, 2                          @ 2 is the only prime even number
 bne last
 mov r0, 1
 b last
odd:
 mov divisor, 3
 cmp  number, 8
 bgt big
 mov r0, 1
 cmp number, 1                          @ 1 is the only odd number < 8 not prime
 bne last
 mov r0, 0
 b last
big:
 mov r0, number
 mov r1, divisor
 bl divide
 teq r1, 0
 beq factor
 add divisor, divisor, 2
 mul tmp, divisor, divisor
 subs tmp, tmp, number
 ble big
 mov r0, 1
 b last
factor:
 mov r0, 0
last:
 ldmfd sp!, {r4-r6, pc}

The isprime function uses a naive, yet straightforward, algorithm to determine whether a given number is prime.

divide.s
.syntax unified
# divide takes value in r0, divisor in r1 and returns dividend in r0 and modulus
 in r1 
 .global divide
 .type divide, %function
divide:
 stmfd   sp!, {lr}
# see http://infocenter.arm.com/help/topic/com.arm.doc.ihi0043d/IHI0043D_rtabi.pdf
 bl __aeabi_uidivmod
 ldmfd   sp!, {pc}

Our divide and long_divide routines are wrappers around the libgcc functions to allow comments.

long_divide.s

.syntax unified
# long_divide takes low numerator in r0, high numerator in r1, low denominator in r2 and high denominator in r3
# returns low quotient in r0, high quotient in r1, low remainder in r2 and high remainder in r3
.global long_divide
.type long_divide, %function
long_divide:
        stmfd   sp!, {lr}
# see https://codereview.chromium.org/5302007/diff/12001/arch/arm/lib/_uldivmod.S
 bl __aeabi_uldivmod
 ldmfd   sp!, {pc}

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