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
    17,751
    4,799
    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
    17,751
    4,799
    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
    17,751
    4,799
    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.
Loading...