Multiplication in MIPS by shifting and adding, without mult

Question

I have the following code, but I keep receiving an Arithmetic Overflow error. The problem that I am trying to solve is multiplying two 31-bit numbers together and storing the results in $t2 $t3 and printing out the correct result. It seems that I have coded for two numbers to be multiplied and the end result is a 31-bit number.

I would love to narrow down where I feel like I am going wrong, but I honestly cannot see where and what I need to change.

# program to multiply two 31 bit binary numbers (A & B),

# using the “shift and add” .

.data

# declare the variable lables of ASCII storage type.

prompt1: .asciiz "Enter number 1: "

prompt2: .asciiz "Enter number 2: "

result: .asciiz "The multiplication of two 31 bit binary numbers is: "

.text

main:

            #prompt1.

            li $v0, 4   

            la $a0, prompt1

            syscall

           #read number 1 and store in the register $t0

            li $v0, 5        

            syscall  

            move $t0, $v0

         

            #prompt2.

            li $v0, 4   

            la $a0, prompt2

            syscall

           

            #read number 2 and store in the register $t1

            li $v0, 5        

            syscall  

            move $t1, $v0

                          

            li $t2, 0 # The final result of the multiplication

                            #is saved into the register $t2

            li $t3, 1 # Mask for extracting bit!

            li $s1, 0 # set the Counter to 0 for loop.

multiply:

            #if the Counter $s1 is equal to 31, then go the lable exit

            beq $s1, 31, exit

            and $s2, $t1, $t3

            sll $t3, $t3, 1

                    beq $s2, 0, increment

            add $t2, $t2, $t0

increment:

            sll $t0, $t0, 1

            addi $s1, $s1, 1

            j multiply

exit:

            #display the result string.

            li $v0, 4   

            la $a0, result

            syscall

                            #display the result value.

            li $v0, 1

            add $a0, $t2, $zero

            syscall

         

            li $v0, 10 # system call code for exit = 10

            syscall   # call operating sys

Sample input A: 1143330295 (Decimal) Sample input B: 999999223 (Decimal)

Your algorithm seems correct, but when you multiply two 32 bits numbers, the result is 64 bits. You are probably using a 32 bits mips and with your algorithm you have an arithmetic overflow. You can use $t3 to store lsb part of the result, and in the loop instead of shifting $t0 in increment, a/ keep the lsb of $t2 in $t4 b/ srl $t2 $t2 1 and srl $t3,$t3,1 c/ reinject the lsb of $t4 in the msb of $t3 by shifting it by 31 and oring it with $t3. — Alain Merigot
I thought the same thing as far as storing part of it in $t3 to avoid the error. I tried implementing what you said but I think I am modifying the wrong parts. You have been extremely helpful so far. I am sure you are going to hate me, but any chance you could modify it based on your comment. I seem to be modifying it wrong. I apologize I am brand new to assembly and it is still a bit hazy, perhaps if I visualized your thought process it would make it much clearer for me. I would greatly appreciate it. I really want to learn how this process works. — rdopler

Alain Merigot Alain Merigot · Accepted Answer · 2019-03-27T12:31:31

Here is a possible implementation.

Differences from your code :

a 32x32 multiplication generates a 64 bit result. On a 32 bits mips, result must be split in two registers
instead of left shifting operand, that will drive to overflows, result is right shifted. Expelled bits are saved and reinjected in lower part of result
use addu for the addition. Numbers are unsigned and without unsigned ops overflows may occur
changed loop in a "do while" form. Loop counter is decremented

Displayed result is presently in two parts. Incorrect display may occur if LSB is set (and is considered as a negative signed by display int syscall)), but most mips simulators do not have a way to display a large unsigned.

# program to multiply two 31 bit binary numbers (A & B),
# using the “shift and add” .

.data
# declare the variable lables of ASCII storage type.
prompt1: .asciiz "Enter number 1: "
prompt2: .asciiz "Enter number 2: "
result: .asciiz "The multiplication of two 31 bit binary numbers is: "
result2: .asciiz "\nand the upper part of result is: "

.text
main:
        #prompt1.
        li $v0, 4   
        la $a0, prompt1
        syscall

        #read number 1 and store in the register $t0
        li $v0, 5        
        syscall  
        move $t0, $v0

        #prompt2.
        li $v0, 4   
        la $a0, prompt2
        syscall

        #read number 2 and store in the register $t1
        li $v0, 5        
        syscall  
        move $t1, $v0

        li $t2, 0 # The final result of the multiplication is 64 bits
                  # MSB part is in register $t2
        li $t4, 0 #  and LSB part of result is in $t4
        li $t3, 1 # Mask for extracting bit!
        li $s1, 32 # set the Counter to 32 for loop.   

multiply:
        and $s2, $t1, $t3
        beq $s2, 0, increment
        addu $t2, $t2, $t0

increment:
        sll $t3, $t3, 1 # update mask
        ##sll $t0, $t0, 1 # useless, we srl result instead
        andi $s4, $t2,1  # save lsb of result
        srl $t2,$t2,1    # t2>>=1
        srl $t4,$t4,1    # t4>>=1
        sll $s4,$s4,31
        or  $t4,$t4,$s4  # reinject saved lsb of result in msb of $t4
        addi $s1, $s1, -1 # decrement loop counter
        #if the Counter $s1 reaches 0 then go the label exit
        beq $s1, $zero, exit
        j multiply

exit:
        #display the result string.
        ## must be changed to take into account the 64 bits of the result
        ## but AFAIK, there is no syscall for that
        ## can be done in two steps t4 and t2
        ## and result is t4+2**32*t2
        #display the result value.
        li $v0, 4   
        la $a0, result
        syscall
        li $v0, 1  # if using mars replace 1 by 36 to print as an unsigned
        add $a0, $t4, $zero
        syscall
        li $v0, 4   
        la $a0, result2
        syscall
        li $v0, 1 # if using mars replace 1 by 36 to print as an unsigned
        add $a0, $t2, $zero
        syscall

        li $v0, 10 # system call code for exit = 10
        syscall   # call operating sys

Multiplication in MIPS by shifting and adding, without mult

1 Answers