MARIE ASM Lang - division on integers (positive/negative)

Question

For learning purposes I am trying to write any integer division in MARIE.

This is standard (hopefully correct) code that divides X by Y with remainder, but only with positive integers.

 LOAD X
 STORE REMAIN
WHILE SUBT Y
 SKIPCOND 800
 JUMP CHECK
DO STORE REMAIN
 LOAD RESULT
 ADD ONE
 STORE RESULT
 LOAD REMAIN
 JUMP WHILE
CHECK SKIPCOND 400
 JUMP END
 STORE REMAIN
 LOAD RESULT
 ADD ONE
 STORE RESULT
END HALT
X HEX XXXX
Y HEX YYYY
RESULT HEX 0000
REMAIN HEX 0000
ONE HEX 0001

How could I make it work for negatives? Probably some IFs and some bit mask maybe, but I am not sure how to do it properly.

Answer 1

Depends how you define it... D/d=[q,r] (Dividend / divisor = [quotient, remainder])

• 5/2 = [2,1] (you have this one)
• -5/-2 = [3, 1] or [2, -1] (x86 way)
• 5/-2 = [-2, 1] (x86) or [-3, -1]
• -5/2 = [-3,1] or [-2, -1] (x86)

(On x86 CPU the sign of remainder r is always the same as sign of dividend D)

If you will take a look on the results above, in each case the absolute values are the same:

• |5| / |2| = [|2|, |1|]

Remainder has the sign of the dividend, quotient has the sign of the dividend XOR divisor ([+, +] == [-, -] == + vs [+, -] == [-, +] == -).

So you can add at the start of your routine a preparation part, which will test each value, and mark into some flag whether it was positive or negative, converting it to positive, do your division, then at current END patch the results by the flags.

Something like (this is my first time ever with Marie Assembly, so take it more like a hint, and correct it where needed, hopefully only syntax, but maybe even logic errors may be there, I did not verify the code works!):

 CLEAR
 / init temporary/result variables to zero
 STORE q_flag
 STORE r_flag
 STORE RESULT
 SUBT X / try (-Dividend) value
 SKIPCOND 800
 JUMP DividendWasPositive / positive or zero
 STORE X / (-Dividend) positive, rewrite original X
 STORE q_flag / set flags to positive value (X)
 STORE r_flag
DividendWasPositive,
 CLEAR
 SUBT Y / try (-divisor) value
 SKIPCOND 400
 JUMP DivisorNotZero
 HALT / division by zero detected, error
DivisorNotZero,
 SKIPCOND 800
 JUMP DivisorWasPositive
 STORE Y / (-divisor) positive, rewrite original Y
 / flip quotient flag value (zero <-> nonzero) ("nonzero" == X)
 LOAD X / will not "flip" anything when 0 == X
 SUBT q_flag / but then q = 0, so it's harmless deficiency
 STORE q_flag / q_flag is now zero or positive (X) value
DivisorWasPositive,
 / here X and Y contain absolute value of input numbers
 / q_flag is positive value when quotient has to be negated
 / r_flag is positive value when remainder has to be negated
 / .. do your division here ..
 / patching results by the q/r flags from the prologue part
AdjustQuotientSign,
 LOAD q_flag
 SKIPCOND 800
 JUMP AdjustRemainderSign
 CLEAR
 SUBT RESULT
 STORE RESULT / quotient = -quotient
AdjustRemainderSign,
 LOAD r_flag
 SKIPCOND 800
 JUMP SignsAdjusted
 CLEAR
 SUBT REMAIN
 STORE REMAIN / remainder = -remainder
SignsAdjusted,
 HALT
q_flag, DEC 0
r_flag, DEC 0
... rest of your variables

Other option may be to have separate variants of routine for each situation (4 variants), as they will differ only in ADD/SUBT Y/ONE and the terminating condition 000 vs 800, which would execute fewer instructions for each case (better performance), but there would be a bit more code lines plus the code above may give you some new ideas, how to do things in Assembly.