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