Friday 7 March 2014

Triangle numbers

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

.syntax unified

.align 2

.section .rodata
resstring:
.asciz "%d\n"

.equ    last, 250       @ we count up to the square root - so half of the divisors will
                        @ be necessarily less than the square root and half above.

icount .req r4          @ it is possible to write FORTRAN in any language :-)
jcount .req r5
tmp    .req r6
num    .req r7

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

@ we use jcount to hold current divisor and icount to hold the number of divisors seen
@ num is passed as r0 and the number of divisors is returned.
get_num_divisors:
 stmfd   sp!, {r4-r7, lr}
 mov     num, r0
 mov     icount, 0
 mov     jcount, 1
jstart:
 mov     r0, num
 mov     r1, jcount
 bl      divide
 teq     r1, 0
 beq     factor
 b       nextj
factor:
 add     icount, icount, 1
nextj:
 add     jcount, jcount, 1
 mul     tmp, jcount, jcount
 cmp     num, tmp
 bgt     jstart
 mov     r0, icount
 ldmfd   sp!, {r4-r7, pc}

.align  2
.global main
.type   main, %function

main:
 stmfd   sp!, {r4-r7, lr}
 mov     num, 0
 mov     icount, 0
 mov     jcount, 1
loop:
 cmp     num, #last
 bge     printme
 add     icount, icount, jcount
 mov     r0, icount
 bl      get_num_divisors
 mov     num, r0

 add     jcount, jcount, 1
 b       loop

printme:
 mov     r1, icount
 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

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