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.

score 1 · Accepted Answer · answered Feb 03 '17 at 14:21

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.

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

1 Answers1