How do I implement multiplication and division in MIPS assembly without using the built in instructions?

Question

Ok, here is the problem. I had to write a MIPS program that got 2 input numbers from the user. Then, I had to write a code that would output the product, quotient and remainder for the 2 numbers entered by the user.

Now, that was pretty straight forward. However, I didnt realize that we could NOT use the multiply and divide operands in the program. Now I dont know what to do because I am confused on how to do it without the multiply and division operands. I only used it twice in the whole program, it works fine but my professor wont accept it and now im getting sad. Any help would be appreciated. Thank you

Here is my code

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

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
syscall

li $v0,4
la $a0, str5
syscall

#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
syscall
# read print string for str4
li $v0, 4
    la $a0, str4
    syscall
# print remainder
li $v0, 1
move $a0, $t1
syscall

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

Answer 1

What you're looking for is bitwise multiplication/division.

I'm not sure I can summarize it succinctly, but here I go with an example:

To Multiply

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

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

To multiply these numbers, you need to shift by the nearest multiple of two below the nummber, then add.

For example, the nearest multiple of 2 below 5 is 4, that is to say it's 2^2;
So we bitwise shift left a (the number 6) 2 times:
a << 2
Which now makes it 00011000

This means we've now multiplied by 4; to now make this multiplied by 5, we simply add a again:

     00011000  
    +00000110  
    =00011110  
    =30 (base 10)

Which is 6*5.

Let's try this again with 12*11 The nearest multiple of 2 below 11 is 8 (2^3). This means we'll need to bitwise shift the number 12 3 times, then add it to itself another 3 times.

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

To Divide

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

Relevant Resource(s)

That's the best I can do right at this moment; if you want more, with relevant algorithms in C, take a look at http://www.programmersheaven.com/mb/CandCPP/295363/295363/bitwise-multiplication--division/

If you want any of this answer expanded, comment below;

P.S. I've shown you two examples with prime numbers (nasty) but what if you get a number like 12? Logically, based on what I've said, the nearest multiple of 2 is 8 (2^3), so you'd have to bitshift left 3, then add 12 to the number 4 times.

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