# Differences

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

— |
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~~ | ||