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
 mov     number, 3                              @ start with 3 as first odd prime
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
 adds    sum_lo, sum_lo, number                 @ and add to sum
 adc     sum_hi, sum_hi, 0
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}

No comments:

Post a Comment