## Thursday, 15 August 2013

### Summing prime numbers

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

```.syntax unified
.equ    word,4

.equ    limit,2000000
.equ    numprimes4,595732                       @ sufficient to hold all the bytes in all the elements of the vector we use to hold the primes

sum_hi          .req r4
sum_lo          .req r5
numprimes       .req r6
primes_ptr      .req r7
number          .req r8
limit           .req r9

.section .bss
.lcomm primes_vector,numprimes4                 @ allocate space for vector of primes
.section .rodata
llustring:
.asciz "%llu\n"
.text
.align 8
.global main
.type main, %function
main:
stmfd   sp!, {r4-r9, fp, lr}
ldr     primes_ptr, =primes_vector
mov     numprimes, 1
mov     number, 2
str     number, [primes_ptr]                   @ store 2 to primes vector
ldr     limit, =limit
mov     sum_hi, 0                              @ initialise sum
mov     sum_lo, 2
loop:
cmp     number, limit
bge     printme                                @ leave if we have exceeded limit

mov     r0, number
ldr     r1, =primes_vector
mov     r2, numprimes
bl      prime_vector
teq     r0, 1                                  @ check for primality of number
bne     nexti
str     number, [primes_ptr, numprimes, lsl 2] @ if prime, add to vector
add     numprimes, numprimes, 1                @ increment prime count
nexti:
add     number, number, 2                      @ increment number by 2
b       loop
printme:
mov     r2, sum_lo
mov     r3, sum_hi
ldr     r0, =llustring                         @ store address of start of string to r0
bl      printf

mov     r0, 0
ldmfd   sp!, {r4-r9, fp, 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
prime_vector:
stmfd   sp!, {r4-r8, lr}
mov     number, r0
mov     vptr, r1
mov     vsize, r2
nexti:
ldr     tmp, [vptr], word                      @ get vector element to tmp
mul     squared, tmp, tmp                      @ and square it
cmp     squared, number                        @ compare the square to the input number
movgt   r0, 1                                  @ store 1 to r0 if square is greater (i.e. number is primes)
bgt     last                                   @ and jump out
mov     r0, number
mov     r1, tmp
bl      divide                                 @ divide number by tmp
teq     r1, 0                                  @ and check if it is a divisor
moveq   r0, 0                                  @ if so, not prime, so set r0 to 0
beq     last                                   @ and leave
subs    vsize, vsize, 1                        @ decrement prime counter
bgt     nexti                                  @ and try next vector element
mov     r0, 1
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}
```