How to implement multiplication and division in MIPS assembly without using inline instructions?

Ok, here's the problem. I had to write a MIPS program that received 2 inputs from the user. Then I had to write code that outputs the product, coefficient and remainder for two numbers entered by the user.

It was pretty straight forward now. However, I did not understand that we cannot use multiply and divide operands in the program. Now I dont know what to do because I am confused on how to do it without multiplying and dividing the operands. I've only used it twice in the whole program, it works great, but my professor doesn't accept it and now I'm getting sad. Any help would be greatly appreciated. Thanks you

Here is my code

# Given positive integers a and b, output a/b and a%b.
str1: .asciiz "Enter a: "
str2: .asciiz "Enter b: "
str3: .asciiz "a/b = "
str4: .asciiz "a%b = "
str5: .asciiz "a*b = "
newline: .asciiz "\n"

main: li   $v0, 4            # system call code for print_string
  la   $a0, str1         # address of str1
  syscall                # print str1

#get the first number from user, put it into $s0

li   $v0, 5            # system call code for read_int
  syscall                # read an integer into $v0 from console
  add  $s0, $v0, $zero   # copy $v0 into $s0 (a)

#read print_string for str2
li   $v0, 4            # system call code for print_string
  la   $a0, str2         # address of str1
  syscall                # print str1

# get second number from user, put it into $t1  
li  $v0, 5      #load syscall for read_int
syscall         #make the syscall
move $s1, $v0       #move the number read into $s1(b)

#DO THE CALCULATIONS................................................
div $s0, $s1        #diving $s0 by $s1
mflo    $t0         #storing value of lo(quotient) in
                #register $t0
mfhi    $t1         #storing value of hi(remainder) in
                #register $t1

mult $s0, $s1
mflo $t2

li $v0,1
move $a0, $t2

li $v0,4
la $a0, str5

#read print_string for str3
li   $v0, 4            # system call code for print_string
  la   $a0, str3         # address of str1
  syscall                # print str1   

#print a/b
li  $v0, 1      #load syscall print_int into $v0
move $a0, $t0      #move the number to print into $t2
# read print string for str4
li $v0, 4
    la $a0, str4
# print remainder
li $v0, 1
move $a0, $t1

#end of program
li  $v0, 10     #system call code for exit



source to share

3 answers

What you are looking for is bitwise multiplication / division.

I'm not sure I can summarize it, but here's an example:


Let's say you want to multiply number 6 by number 5.
If a = number 6, then (in simplified 8-bit) it is: a=00000110

If b = number 5, then (in simplified 8-bit) this: b=00000101

To multiply these numbers, you need to shift the closest few of the two below nummber and then add.

For example, the closest multiple of 2 below 5 is 4, that is, 2 ^ 2,
so we shift left bitwise a

(number 6) 2 times:
a << 2

Which now does it00011000

This means that we have now multiplied by 4; to now multiply by 5, we simply add a


    =30 (base 10)


What is 6 * 5.

Try again with 12 * 11 The closest multiple of 2 below 11 is 8 (2 ^ 3). This means that we need to bitwise shift 12 3 times and then add it ourselves 3 more times.

    00001100 = 12
    //Let bitshift by 3
    01100000 = 96
    //Let add 12 3 times
   =01101100 = 108
   =01111000 = 120
   =10000100 = 132 = 12*11



To divide 12 by 11, you go the other way; subtract 12 from 132, 3 times, then shift the bits right 3 times (divide by 8)

Relevant resource (s)

This is the best I can do at this moment; if you want more, with related algorithms in C, have a look at

If you would like any of these answers to be expanded on, comment below;

PS I showed you two examples with prime numbers (nasty), but what if you get a number like 12? Logically from what I said, the closest multiple of 2 is 8 (2 ^ 3), so you would need to shift the bit to the left 3 and then add 12 to the number 4 times.

But if you do the math, you find that 12 is actually = (2 ^ 3 + 2 ^ 2) ... which means you can get (12 <3) (that's 12 bits left shift 3 times). then add it to (12 <2) (that's 12 bit-bits left 2 times) ... magic!



Try this for the multiplication algorithm: This is the MIPS implementation of Boothe's algorithm:



From Wikipedia entry on multiplication :

"Since the result of the integer scaling can be considered to consist of a number of copies of the original, integer products greater than 1 can be calculated by re-adding."

In other words, to multiply a * b, you add b times together.

The strategy you mentioned in your comment (bitrate) is interesting - probably more efficient, but definitely much more complicated.

A similar strategy will work for division / remainder.



All Articles