Differences

This shows you the differences between two versions of the page.

Link to this comparison view

blog:jjolly:only_because_i_could [2009/10/21 07:38] (current)
jjolly created
Line 1: Line 1:
 +====== 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 [[http://​uvu.edu|UVU]] and the class uses the [[http://​highered.mcgraw-hill.com/​sites/​0072467509/​|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:
 +
 +<​code>​
 + 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
 +</​code>​
 +
 +Special thanks to [[http://​users.ece.utexas.edu/​~patt/​|Yale Patt]] of [[http://​www.utexas.edu/​|The University of Texas at Austin]] for [[http://​users.ece.utexas.edu/​~patt/​08f.306/​LabAssignments/​Lab1/​index.html|providing me the information]] for my [[http://​i281.photobucket.com/​albums/​kk212/​DougD24/​picard-facepalm.jpg|"​Oh Duh"]] moment (it's in hint#2).
 +
 +{{tag>​programming lc3 puzzles}}
 +
 +~~LINKBACK~~
 +~~DISCUSSION~~