Tuesday, 2 July 2013


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
 .asciz "%d\n"
 .align 2
 .global main
 .type main, %function
 stmfd sp!, {r4-r8, lr}

 mov total, 1
 mov try_product, 1
 mov number, 2
 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
 mov tmp, number
 mov last, tmp
 cmp tmp, limit
 bgt last_mul
 mov last, tmp
 mul tmp, tmp, number
 b prod_loop
 mul total, total, last
 cmp try_product, 0
 bne nexti
 mul total, total, number
 cmp number, limit
 beq printme
 add number, number, 1
 b loop
 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
.align 2

 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
 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
 cmp r1, 15
 bne last
 mov r0, 0
 ldmfd sp!, {pc}

No comments:

Post a Comment