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. .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
source to share
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:
If b = number 5, then (in simplified 8-bit) this:
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
(number 6) 2 times:
a << 2
Which now does it
This means that we have now multiplied by 4; to now multiply by 5, we simply add
00011000 +00000110 =00011110 =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 01100000 +00001100 =01101100 = 108 +00001100 =01111000 = 120 +00001100 =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 http://www.programmersheaven.com/mb/CandCPP/295363/295363/bitwise-multiplication--division/
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!
source to share
Try this for the multiplication algorithm: This is the MIPS implementation of Boothe's algorithm: http://code.google.com/p/mips-booth-multiplication/source/browse/trunk/booth.asm?r=9
source to share
"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.
source to share