# Multiplication of large numbers in MIPS

Discussion in 'Programmer's Corner' started by J_Rod, Oct 5, 2015.

1. ### J_Rod Thread Starter Member

Nov 4, 2014
109
6
Hi,
I am in a lot of trouble right now. MIPS an assembly language programming. I need to implement multiplication in my program for numbers exceeding the 32 LO bit register. Here is my code to try to find 66 000 000^2. I will enter a number and try to find its square. Then the LO register will be printed followed by the HI register. Multiplication in MIPS by the multu command stores the result in a LO and HI register since the registers only store 32 bits.

.data
num_1: .word 66000000
space: .asciiz " "

.text
main:
lw \$t0, num_1

multu \$t0, \$t0
mflo \$t1
li \$v0, 1
move \$a0, \$t1 # print t1, LO register
syscall
li \$v0, 4
la \$a0, space
syscall
mfhi \$t2
li \$v0, 1
move \$a0, \$t2 # print t2, HI register
syscall

li \$v0, 10
syscall

Generates the results: 1218723840 1014210

When I ran the program with num_1 = 66000, the results were: 61032704 1
This shows 66000^2 -1*2^32 = 61032704
66000^2 = 1*2^32 +61032704
The LO register stored 61032704 and the HI register stored 1. In the run above, the LO register stored 1218723840 and the HI register stored 1014210.
66 000 000^2 = 1014210*2^32 +1 218 723 840

My question is how can I work with these large numbers in MIPS if the registers only store 32 bits? By work with, I mean I will need to multiply/divide the result 66000000^2 and print out the answer somehow. Well, with numbers on that magnitude, but not those exact numbers. Anybody with any theory here is wonderful. Thanks all.

Last edited: Oct 5, 2015
2. ### WBahn Moderator

Mar 31, 2012
18,093
4,920
Just think about how you do multiplication of multidigit numbers by hand. Imagine you have only store one digit in a given register and that when you multiply two one-digit numbers together you get, in general, a two-digit number but the results are placed in two different registers. So simply multiply two two-digit numbers together by hand keeping track of how you handle the individual digits as you go and then develop an algorithm that mimics it.

J_Rod likes this.
3. ### J_Rod Thread Starter Member

Nov 4, 2014
109
6
Hmm, I'm still a bit confused on the implementation. I think I will have to examine the bits of each register and then shift them and add. For example, if I had 44*31, I would need to add 44 +1320. In two digit registers, I would have one containing 44, one with 32, and one with 01. Then I would add the 2 +4 = 6 and replace 4 to get 64. Then shift the 32 to 33, and then replace the 3 with 1 to get 13. Then just print the two registers to get 1364. And the implementation would have to be in binary because the assembly language uses binary, right?

4. ### WBahn Moderator

Mar 31, 2012
18,093
4,920
Think about how you do it on paper:

So you have the right 4 in location x0 and the other 4 in location x1.
You then have the 1 in location y0 and the 3 in location y1.
You have four locations for the result, z0 through z3.

Now how would you do it by hand?

You multiply the 4 by the 1 (x0 by y0) and get 04. The 4 is in register p0 and the 0 is in register p1.

You now set the low location of the final result, z0, equal to p0 and the next place up, z1, to p1.

Now you multiply the other 4 by the 1 (x1 by y0) and these results are now in p0 and p1. How do you use these values to update your final result locations?

J_Rod likes this.
5. ### J_Rod Thread Starter Member

Nov 4, 2014
109
6
Initially each place digit is 0.
... ... x1 x0
... ... y1 y0
-------------
z3 z2 z1 z0

multiplicands:
x1 x0 = 44
y1 y0 = 31
iteration 1: x0y0 = p1p0, 4*1 = 04
z0 = z0 +p0, 0 +4 = 4
z1 = z1 +p1, 0 +0 = 0
iteration 2: x1y0 = p1p0, 4*1 = 04
z1 = z1 +p0, 0 +4 = 4
z2 = z2 +p1, 0 +0 = 0
iteration 3: x0y1 = p1p0, 4*3 = 12
z1 = z1 +p0, 4 +2 = 6
z2 = z2 +p1, 0 +1 = 1
iteration 4: x1y1 = p1p0, 3*4 = 12
z2 = z2 +p0, 1 +2 = 3
z3 = z3 +p1, 0 +1 = 1
product:
z3 z2 z1 z0 = 1364
Then tracing this by hand I got the correct answer. I'm a little dense here, but how can this be used to work with the HI and LO registers?

Last edited: Oct 5, 2015
6. ### WBahn Moderator

Mar 31, 2012
18,093
4,920
Think of each 32-bit value as a single digit stored in a single location. When you multiply two 32-bit numbers together, the results are stored in two 32-bit locations -- HI and LO. In the hand example, we called them p1 and p0, respectively.

J_Rod likes this.