Tag Archives: euler

Project Euler 01: 68k Assembly – better version

Posted on by
2

Previously I posted a naive implementation of an algorithm to solve Project Euler problem 1 with Easy68k. Below is a slightly cleverer version which takes advantage of some properties of arithmetic progressions.

In a nutshell, we work out the sum of elements which are multiples of 3, and the sum of elements which are multiples of 5. This also includes the sum of elements which are multiples of 15, so we subtract that value for the total.

The number of instructions overall is larger, but the other version takes 335308 cycles to reach a result, while this version takes only 1308 – a whopping 256% speed increase!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

	org	$1000
start:
 
	; Calculate sum of multiples of 3 and 5 between
	; 0 and 999. calculates the sum of an arithmetic
	; progression.
	; sum = sumprogression(3) + sumprogression(5) - sumprogression(15)
 
	; get progressive sum for 0..999 step 3
	move.l	#3,d0
	move.l	#0,d1
	move.l	#limit,d2
	bsr	sumprogression
	move.l	d0,d6
 
	; get progressive sum for 0..999 step 5
	move.l	#5,d0
	bsr	sumprogression
	add.l	d0,d6
 
	; get progressive sum for 0..999 step 15
	move.l	#15,d0
	bsr	sumprogression
	sub.l	d0,d6
 
	move.l	#3,d0		; output result
	move.l	d6,d1
	trap	#15
	move.b	#9,d0		; halt simulator
	trap	#15		
 
; Works out the sum of an arithmetic progression
; of s(n) = s(n - 1) + d0, starting at d1 up to d2
; result is stored in d0
sumprogression:
	; Save registers
	movem.l	d1,-(a7)
	movem.l	d2,-(a7)
	movem.l	d3,-(a7)
 
	; Caculate the number of terms in the range
	; n = max value / step
	; d3 = d2 / d0
	move.l	d2,d3
	divu	d0,d3
	swap	d3		; clear remainder
	clr.w	d3
	swap	d3
 
	; Get the largest term in the range
	; nth term =  step + ((n - 1) * step)	
	; d2 = d0 + ((d3 - 1) * d0)
	move.l	d3,d2		; Calculate n - 1
	sub.l	#1,d2
	mulu	d0,d2		; (n - 1) * step
	add.l	d0,d2		; step + ((n - 1) * step)
 
	; Find the sum
	; sum = n * (step + nth term) / 2
	; d0 = (d3 * (d0 + d2)) / 2
	add.l	d2,d0		; step + nth term
	mulu	d3,d0		; n * (step + nth term)
	asr.l	#1,d0		; (n * (step + nth term)) / 2
 
	; Restore register values
	movem.l	(a7)+,d3
	movem.l	(a7)+,d2
	movem.l	(a7)+,d1
 
	rts
limit	equ	999		; We are searching for numbers between 0 and 999.
	end	start

It was much, much easier to write this in C# first and then translate it to assembly, and it also helped double check the result:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

namespace Euler1B
{
    class Program
    {
        static int ProgressionSum(int step, int max)
        {
            int n = (max) / step;
            int nth = step + ((n - 1) * step);
            return n * (step + nth) / 2;
        }
 
        static void Main(string[] args)
        {
            int sum3 = ProgressionSum(3, 999);
            int sum5 = ProgressionSum(5, 999);
            int sum15 = ProgressionSum(15, 999);
            int total = sum3 + sum5 - sum15;
            Console.WriteLine(ProgressionSum(3, 999) + ProgressionSum(5, 999) - ProgressionSum(15, 999));
            Console.ReadLine();
        }
    }
}

Project Euler 01: 68k Assembly

Posted on by
4

Recently I’ve been fiddling some 68k assembly with Easy68k (social life? Pah!). One of the joys of 68k assembly is that it is incredibly easy to learn because of the simple architecture. Easy68k provides a nice emulation environment with simple IO, graphics and a device simulator. I wanted to explore x86 assembly but have found it quite demanding, and thought this might be a great place to start (alongside my faithful Third Edition of Alan Clements’ Priciples of Computer Hardware).

Here is an algorithm to solve Project Euler problem 1. This is a naive version simply counts from 1 to 999 and adds values that are multiples of 3 or 5 (lines 7 to 32).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

	org	$1000
start:				; first instruction of program
	clr	d1		; init loop variable
	clr	d2		; init total
loop:
	; Looping condition
	cmp	#limit, d1	; has counter hit limit yet?
	beq	endloop		; yes - jump to the end
	add.w	#1,d1		; increment counter
 
	; Check if d1 % 3 == 0
	move.w	d1,d3		; copy counter for division
	divs	#3,d3		; divide by 3 - remainder in upper word of d3
	clr.w	d3		; clear the result (lower word of d3)
	swap	d3		; swap remainder with result
	cmp.w	#0,d3		; compare remainder with 0
	beq	add		; if remainder is 0, add the number
 
	; Check if d1 % 5 == 0
	move.w	d1,d3	
	divs	#5,d3
	clr.w	d3
	swap	d3
	cmp.w	#0,d3
	beq	add
 
	jmp	loop		; jump to top of the loop
 
	; Add a value to the total
add:	
	add.l	d1,d2		; add value in d1 to the total
	bra	loop		; jump to top of the loop
 
	; End of the loop/output
endloop:
	move.l	d2,d1		; move result into d1 for ouput
	move.w	#3,d0		; output the number
	trap	#15
	move.b	#9,D0		; halt simulator
	trap	#15		
 
; Variables & data
limit	equ	999		; We are searching for numbers between 0 and 999.
	end	start		; last line of source

A cleverer version might use the properties of arithmetic progressions to avoid looping through all the possible numbers in the range, but I’m still battling with that at the moment.