Tuesday, 23 July 2013

Pythagorean triplets

A Pythagorean triplet is a set of three natural numbers, a <b <c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

.syntax unified
.equ limit,1000

.align 4

icount .req r4           @ use of i, j and k as loop indices is historic :-)
jcount .req r5           @ we use icount for a, jcount for b and kcount for c
kcount .req r6
tmp    .req r8
jksum  .req r9

.section .rodata
.asciz "%d\n"
.global main
.type   main, %function
 stmfd sp!, {r4-r9, lr}
 ldr icount, =limit
 subs jcount, icount, 1    @ i > j so start j at i-1
 beq nexti
 subs kcount, jcount, 1    @ j > k too
 beq nextj
 add tmp, icount, jcount
 add tmp, tmp, kcount
 cmp tmp, #limit
 bne nextk
 mul jksum, kcount, kcount @ we re-use the register later as jksum (this is ksquared here)
                           @ we could also alias ksquared to r9 - but then we have to avoid 
                           @ collision with jksum
 mul tmp, jcount, jcount   @ could alias jsquared to r8 (or just re-use tmp) as here
 add jksum, jksum, tmp
 mul tmp, icount, icount   @ and also could alias isquared 9but choose to reuse tmp)
 cmp jksum, tmp            @ this is the important comparison - if i*i == (j*j) + (k*k) 
 beq printme               @ then leave since there is only one solution
 add tmp, icount, jcount
 subs kcount, kcount, 1
 bne kstart
 subs jcount, jcount, 1
 bne jstart
 subs icount, icount, 1
 bne istart
 mul tmp, icount, jcount
 mul tmp, tmp, kcount
 mov r1, tmp
 ldr r0, =resstring
 bl  printf

 mov r0, 0
 ldmfd sp!, {r4-r9, pc}
 mov r7, 1
 swi 0

No comments:

Post a Comment