How can I get this MARIE program for multiplication to work for negatives?

Question

I wrote this program that will multiply two numbers together but now I need to make it work for negative numbers, anyone have any advice?

           Input a         / first factor
           Store a         / store first factor
           Input b         / second factor
           Store b         / store second factor
           Load a          / load first factor
           Skipcond 800    / checks if number is greater than zero
           Jump End        / skips to the end if zero
           load b          / load second factor
           Skipcond 800    / checks if number is greater than zero
           Jump End        / skips to the end if zero
Loop,      Load b          / reloads second factor
           Subt One        / subtracts one from the second factor
           Store b         / store the new value of the second factor
           Load productAB  / load the product of the two number; initially zero
           Add a           / add first factor to the product
           Store productAB / store new value to product
           Load b          / load second factor again
           Skipcond 400    / end loop if b is equal to 0
           Jump Loop       / repeats the loop
           Load productAB  / load the value of productAB; no longer 0
End,       output          / print out results
           Halt            / end of program

a,         Dec 0
b,         Dec 0
productAB, Dec 0 / product of the first two numbers
One,       Dec 1

Answer 1

Your code does not assemble: Input takes no operand, so Input a is invalid.

Less of a problem, but:

• Your program does not output a product even when one of the inputs is 0, so you'll need to support that too.

• If your program is restarted, it doesn't start with a reset product. It is good practice to add code that initialises variables that assume a starting value.

As to supporting negative operands: you should make sure that the operand from which you subtract 1 is not negative. If so, then toggle the sign of both operands. It is not a problem when the other factor is negative, as that works fine with the ADD you perform.

Here is the updated code:

           Clear
           Store productAB    / Reset product
           Input
           Store a
           Input
           Store b
           Skipcond 000       / is B is less than zero?
                    Jump Loop /    no: B >= 0, we can start
           / yes: Negate both A and B
           Clear
           Subt  a
           Store a            / Now A := -A.
           Clear
           Subt  b
Loop,      Store b            / B is now positive
           Skipcond 800       / is B greater than zero?
                    Jump End  /      no: it is 0; we're done
           Load  productAB  
           Add   a            / Product += A
           Store productAB  
           Load  b
           Subt  One          / B--
           Jump  Loop
End,       Load  productAB
           Output             / Print the product
           Halt

a,         Dec 0
b,         Dec 0
productAB, Dec 0 / Product of the first two numbers
One,       Dec 1

Assemble & run on MARIE.js.org.

Answer 2

Here's the pseudocode for an optimized version of a multiplication algorithm that works for all integers:

    product = 0
    is_negative = False

    if a < 0 and b > 0 or a > 0 and b < 0:
        is_negative = True

    # make both a and b positive
    if a < 0:
        a = -a
    if b < 0:
        b = -b

    # a should be the bigger number
    if a < b:
        temp = a
        a = b
        b = temp

    # perform multiplication
    for i in range(0, b):
        product += a

    if is_negative:
        return 0-product
    return product

By implementing a swapping feature, the code takes less iterations when multiplying a large number and a small number. For example, when multiplying 1000*2, the revised algorithm simply does 1000+1000 instead of 2+2+...+2.

Here's the corresponding MARIE.js code:

input
store a

input
store b

jns check_sign
jns make_a_pos
jns make_b_pos
jns mult

/ check true sign of product
load negative
Skipcond 400
jump output_negative_product
/ Output  positive product
load product
output
halt
 
check_sign, hex 0
            load a
            Skipcond 000
            jump check_sign_given_a_pos/ do if a >= 0
            
            / if a < 0
            load b 
            Skipcond 000
            jump set_neg_true / a < 0 and b > 0
            JumpI check_sign / a < 0 and b < 0

check_sign_given_a_pos,     load b 
                            Skipcond 000
                            JumpI check_sign / a >= 0 and b >= 0
                            jump set_neg_true / a >= 0 and b < 0

/ negative = 1 and returns to main
set_neg_true,   load one
                store negative
                JumpI check_sign

/ a =  abs(a)
make_a_pos,     hex 0
                load a
                Skipcond 000
                jumpi make_a_pos
                load zero
                subt a
                store a
                jumpi make_a_pos
                
/ b = abs(b)
make_b_pos,     hex 0
                load b
                skipcond 000
                jumpi make_b_pos
                load zero
                subt b
                store b
                jumpi make_b_pos
 
output_negative_product,    load zero
                            Subt  product
                            store product
                            output
                            halt
                    

/ performs product = abs(a) * abs(b), where abs(a) >= abs(b)            
mult,   hex 0
        load a
        subt b
        
        / a < b ?
        skipcond 000
        Jump mult_loop
        
        / swap a and b
        load a
        store temp
        
        load b
        store a
        
        load temp
        store b
        
mult_loop,  load i
            subt b
            / i < b ?
            skipcond 000
            JumpI mult

            load product
            add a / product += a
            store product

            / i++
            load i
            add one
            store i

            jump mult_loop

negative, dec 0 / initially false. 
one, dec 1 
zero, dec 0
i, dec 0
temp, dec 0
a, dec 0
b, dec 0
product, dec 0

Answer 3

Using pseudo code

neg = 0
if (a < 0)
    a = -a
    neg = 1
if (b < 0)
    b = -b
    neg ^= 1
productAB = a * b
if (neg)
    productAB = -productAB