CSE 410

CSE 410 HOMEWORK POLICY Spring 2003

Homeworks will be given out each Thursday normally, and will be due the following Thursday in class. Late homeworks will not be accepted.

HOMEWORK #1 Due: Thursday April 10

1a.Take the following machine language code and rewrite it in assembly language. Assume that the instructions are stored in sequential locations, starting at address 100.

0100:	1 1 1 2	start:		load		a
0101:	3 1 1 3			add		one
0102:	2 1 1 2			store		a
0103:	5 1 1 2			mul		a
0104:	4 1 1 1			sub		x
0105:	8 1 0 7			brpos		out
0106:	7 1 0 0			br		start
0107:	1 1 1 2	out:		load		a
0108:	4 1 1 3			sub		one
0109:	2 1 1 2 		store		a
0110:	0 1 2 3			halt
0111:	0 0 7 9	x:		number 		79
0112:	0 0 0 1	a:		number 		1
0113:	0 0 0 1	one:		number		1

b. What does the program do?

Computes the largest integer approximation to sqrt(x). In other words, it finds a such that a² ≤ x and (a+1)²> x, which since x is 79 in this case, is 8.

2a. Write an assembly language program to compute the greatest common divisor (gcd) of two positive integers m and n. (The gcd is the largest integer that evenly divides both m and n. Thus, gcd(20,8)=4, gcd(7,25)=1, gcd(9,27)=9 ) Use the following variation of Euclid's algorithm:

top:	load		x
	sub		y
	brpos		xgtr	; if x>y
	load 		y
	sub		x
	brpos		ygtr	; if y>x
	halt			; we get here only if x==y
xgtr:	store		x	; x=x-y
	br		top	; iterate again
ygtr:	store		y	; y=y-x
	br		top	; iterate again
x:	number		xxxx	; this stores x
y:	number		yyyy	; this stores y

We assume that the values for x and y are placed in the given locations before calling this code. When we are done, the gcd is in x and y.

There are a lot of other solutions that work, and we accepted those too.

There were two very common errors:

Using raw addresses rather than using labels for branch targets and for arguments to load/store and arithmetic operations. Use labels! The idea behind assembly language is that it is easier to program in than machine language – the assembler computes all the addresses for you. The code is clearer to read. Also, if you insist on using raw addresses and later decide to insert a new instruction into your code, you have to recompute ALL the addresses in your code, a time-consuming and error-prone process.
Not allocating space for parameters and constants. You need to do this. It is also best to put your data right after your code because it fragments the computer’s memory less.

b. Assemble your program into machine language, starting at location 537.

Addr	code
537:	1548	top:	load		x
538:	4549		sub		y
539:	8544		brpos		xgtr	; if x>y
540:	1549		load 		y
541:	4548		sub		x
542:	8546		brpos		ygtr	; if y>x
543:	0000		halt			; we get here only if x==y
544:	2548	xgtr:	store		x	; x=x-y
545:	7537		br		top	; iterate again
546:	2549	ygtr:	store		y	; y=y-x
547:	7537		br		top	; iterate again
548:	0000	x:	number		xxxx	; this stores x
549:	0000	y:	number		yyyy	; this stores y

We included the assembly language program for clarity.