2
\$\begingroup\$

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
\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$

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.
\$\endgroup\$
3
  • \$\begingroup\$ I don't think Project Euler problems specify which algorithm is to be used. They simply require that code produces the correct result in a reasonable time. The part about using a simpler O(1) algorithm still holds of course. \$\endgroup\$ Jan 16, 2022 at 16:43
  • \$\begingroup\$ @TobySpeight No, Project Euler doesn't specify which algorithm is to be used. If fact, using the steps laid out in the problem usually leads to a time prohibitive approach. PE is more math/logic challenges than programming challenges. That being said, it is a great playground for experimenting with new languages. In this case, I'd say I identified a mistake. The algorithm adds whole numbers where as the problem explicitly stated natural numbers. Including zero in the sums doesn't matter for the calculation, of course, but it is technically wrong. \$\endgroup\$
    – AJNeufeld
    Jan 17, 2022 at 18:38
  • 1
    \$\begingroup\$ Just thinking about the O(1) solution, I don't think it does need DIV. There are a handful of places we need to divide, but in all cases the denominators are constants (3, 5, 15 and 2), so can be transformed into multiplication and bit-shifting. \$\endgroup\$ Jan 17, 2022 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.