Only because I could...

I managed to write an algorithm that would perform 16-bit long division using just the ADD, AND and NOT operators of the LC-3 machine simulator.

Just to make sure everyone understands, I am teaching an assembly language class at UVU and the class uses the LC-3 machine simulator. It's nice, but it has a grand total of three arithmetic operators: ADD, AND and NOT. Subtraction is done by performing a 2s complement inversion on the number being subtracted, then performing addition. Division could be performed by counting the number of subtractions of the denominator from the numerator, but this method scales horribly. Long division would be nice, but you probably noticed the lack of a bitwise shift operator in my list of arithmetic operators.

This stymied me for a while, until last night when I was reminded that left-shifting bits will multiply a number by two, thus adding a number to itself is a fine simulation of the left-shift operator. This is actually so stinking obvious that I feel the need for penance for my obvious act of slothfulness.

So, here's what I did. One LC3 register was maintained for the original numerator and would be rotated through the range of 16-bits. Another register would maintain a bitmask to allow only the bits that had been rotated. This would allow me to subtract the denominator from only the rotated bits. For every successful positive subtraction I would shift in a bit the last register - the quotient. When the bitmask became negative (the high-bit was set), then I was done.

Again, obvious. Here's the code I wrote in about 30 minutes at 11:00pm last night:

	NOT	R3, R1
	ADD	R3, R3, #1	; R3 will be the subtracting denominator
	ADD	R1, R0, #0	; R1 will be the rotated numerator
	AND	R0, R0, #0	; R0 will be the advancing quotient
	AND	R2, R2, #0	; R2 will be the numerator bitmask
DIVROLL	ADD	R2, R2, #0	; First, are we done?  Test if the bitmask is negative
	BRn	DIVSIGN
	ADD	R2, R2, R2	; Shift mask left and add one
	ADD	R2, R2, #1
	ADD	R0, R0, R0	; Shift the quotient left
	ADD	R4, R1, R1	; Roll numerator
	ADD	R1, R1, #0
	BRzp	DIVRLBT
	ADD	R4, R4, #1	; Roll the high bit into the low
DIVRLBT	ADD	R1, R4, #0
	AND	R4, R1, R2	; Mask
	ADD	R4, R4, R3	; Test
	BRn	DIVROLL
	ADD	R1, R1, R3	; Subtract from numerator and set a bit in the quotient
	ADD	R0, R0, #1
	BRnzp DIVROLL		; And do it again

Special thanks to Yale Patt of The University of Texas at Austin for providing me the information for my "Oh Duh" moment (it's in hint#2).

You could leave a comment if you were logged in.