Project Euler 1 (sum of multiples of 3 or 5) in ARM Assembly

Question

Project Euler #1 asks:

Find the sum of all the multiples of 3 or 5 below 1000.

In ARM Assembly;

• I did this in 3 loops, which avoids any MOD or DIV.
• Each loop is written out, without a common subroutine, since loop 3 is different than loops 1 and 2, and the space savings in combining 1 and 2 are negated by the bl / bx lr.

All suggestions appreciated:

lim     equ     1000

euler1  
        mov     r0, #0

        mov     r1, #0 ; i = 0
nexti3  
        add     r0, r0, r1 ; a += i
        add     r1, r1, #3 ; i += 3
        cmp     r1, #lim
        blt     nexti3 ; if (i < lim) goto loop

        mov     r1, #0
nexti5  
        add     r0, r0, r1
        add     r1, r1, #5
        cmp     r1, #lim
        blt     nexti5

        mov     r1, #0
nexti15 
        sub     r0, r0, r1
        add     r1, r1, #15
        cmp     r1, #lim
        blt     nexti15

Answer 1

Algorithm

Looking at the code, it is not solving Project Euler #1, which asks for

S = 3 + 5 + 6 + 9 + ... + 995 + 996 + 999

Your code is solving ...

S = + 0 + 3 + 6 + 9 + ... + 999 + 0 + 5 + 10 + ... + 995 - 0 - 15 - 30 - ... - 990

... which looks like steps for a completely different problem. In short, you've done some work to transform the algorithm from something that needs to test if a value is a multiple of 3 or 5, to a different algorithm which simply sums multiples. You could do more work and simplify into an algebraic formula with no looping at all (although you would need to use DIV).

If you were asked a slightly different problem, the extra 0's being used in your loops could become an issue. For instance, if asked for the product instead of the sum, your formulation would have your first step multiplying by 0! You could easily skip the zeros using mov r1, #3, mov r1, #5 and mov r1, #15 instead of the three mov r1, #0 statements.

Code

You've got a hard coded limit. The problem indicates that the value 23 would be returned if you use a limit of 10, and then asks for the value returned for a limit of 1000. Would you write completely different code if you wanted to evaluate with the first limit? Probably not.

Instead, write the code as a function. The input parameter limit would be placed in r0 before calling the function (bl euler1). Move it into r2 inside the function, and then replace occurrences of cmp r1, #lim with cmp r1, r2. The result is left in r0 for when the function returns. You're now using additional registers (r2 as well as the link register), but the function can validate the problem's test data before computing the actual answer:

    ; Test case to verify implementation
    mov r0, #10
    bl euler1
    cmp r0, #23          ; Did it work?
    bnz assert_failure

    ; Solve actual Project Euler 1 problem
    mov r0, #lim
    bl euler1
    ; r0 should have actual answer here.