Re: MIPS - Making a 64 bit number when you only have 32 bit register support

[Kerren]

Hey guys I've been working on this program for just over a week now and I just can't seem to find any way around my problem. The problem I'm having is:

I'm trying to add 32 bit numbers together and if there is an overflow then I'd like to find a way to output the result as a 64 bit number.

I had a couple of ideas (as of yet, none of them have worked ) so here they are:

1. My first bright idea
   I tried to add numbers together and when there was an overflow I'd increment another register (lets call it the "overflow" register). Once the calculation was done I would just output the overflow register next to the other register to make a "64 bit" number In theory this would work IF we were working in decimal (base 10) because when there is an overflow a digit is added to the front of the result, however, in binary there is not always a whole new digit added to the front of the result so this didn't work for me and I got some pretty funny answers !
   
2. The second idea
   I tried to allocate 8 bytes in the heap memory block and just save the result to that. The problem I had is that I can't dereference that allocated memory in the actual add function. This means that I have to use an intermediate register for calculating the result and then I would copy this intermediate register to the allocated memory. This defeats the point of the allocated memory because the intermediate register is only 32 bits
   
3. The third (untested) idea
   I want to read in an actual binary input and then I can shift the bits and if there is an overflow I add them to a new binary number (the overflow register) and then output both the overflow register and the result register together to form a 64 bit number. The problem I'm having is that I don't actually know how to make a binary variable (is there even such a thing as a "binary variable" ??)
   
4. The fourth idea
   I tried to use the $f register because it looks to me like they are 64 bit registers but it seems like they are private registers that I cannot access. Does anyone know any way around this?
   
5. Other thoughts
   Is there any way to link registers together so that they can form virtual 64 bit ones (I know that's a really hopeful thought )?
   
   Also does anyone have any other ideas on how to make a 64 bit system using only 32 bit registers?

Thanks guys!

*** Edit ***
I originally posted this to the Electrical Engineering forum by mistake so I just copied it here 12/08/2012

 

[rcgldr]

MIPS doesn't have borrow or carry bits, so you have to code around this. If an 32 bit unsigned add would produce a carry, then the 32 bit lower sum will be less than either of the 32 lower order addends (input). You can use SLTU to take advantage of this fact. For subtract, you can use SLTU to check for a borrow condition in the low order registers. You'll want to use the unsigned add and subract instructions. For signed numbers you'll need to do an overflow check on the high order operation.

 

[Kerren]

Awesome thanks for the reply rcgldr ! If I do take the overflow into account and add it to a new registry, is there even a way to correctly output the 64 bit number?

As in:

If I have two registers, a high and a low, and whenever there is an overflow then I increment the high register, is there a way to get the actual decimal result between these two registers?

Thanks !

 

[rcgldr]

If I do take the overflow into account

Overflow is only used for signed math, and for extended precision numbers would only be used for the most significant portion of signed numbers.

Is there a way to get the actual decimal result between these two registers?

That would be more difficult. You would need to implement an extended divide operation. One way to implement this would be to split up a 64 bit number into four 16 bit numbers using the lower 16 bits of registers. After each divide step, the remainder is used as the upper 16 bits for the next divide step (for the first step, the upper 16 bits would be zero). An alternative would be to have a large table of 64 bit numbers that represent powers of ten and do repetitive subtractions.

 

[Kerren]

Awesome! I'm going to try dividing the number into 4X16 bit registers and see if I can make it work ! Thanks so much for the help rcgldr !

 

[rcgldr]

Awesome! I'm going to try dividing the number into 4X16 bit registers and see if I can make it work.

Note, the simplified method I described only works when dividing the large number (64 bits in this case) by a number 16 bits or less in size. Since you want to convert the number to decimal, you could divide by 10 to get one digit at a time or divide by 10,000 to get 4 digits at a time (using the regular instructions to break up each set of 4 digits). Both 10 and 10,000 are less than 16 bit in size, so the simplified method will work.

Otherwise, to divide large numbers by large numbers, you'd need something like long hand division, where you make a "guess" at the quotient, and do a multiply and subtract step, iterating 2 or 3 times for each "word" of quotient. For really big numbers, there are complex algorithms based on Fourier Transforms, finite field (modulo) math, ..., to speed up the process, but I doubt you'd need any of this stuff for what you're doing with the MIPS projects.

 

[Kerren]

Hi rcgldr thanks so much for the help! Unfortunately I couldn't get the output to work so I switched to a different approach, I also made it a multiply instead of just an add function:

I made my result hi and result low registers the same as the mult hi and low registers.

In case anyone ever needs to know how here's a short explanation:

If we are to multiply 2 numbers in binary form there are many ways to do it without the mult function. Firstly if you want to do something like 8x5 you could add 8 to a result 5 times ie 8x5 = 8 + 8 + 8 + 8 + 8. Another way to do it is to loop through the binary representation of the number and every time you go through the loop - shift the multiplicand by one bit, now look at the multiplier, if the multiplier bit is 1 then add it to the result otherwise skip the add and continue the loop. Example:

So this is all great and it works like a charm!... for small numbers, but what happens when you shift a binary number 30 times or more??

What you need is a high register for your multiplicand, when you shift it too high you need to shift it into this high register. You can actually add this high register to the result high register right from the start of the loop because at the start this "multiplicand high register" will be zero so you will effectively be adding nothing.

That takes care of the multiplicand being shifted too much, another problem can occur when the result register actually has a carry bit. In this case you just add 1 to the result high register. Why? Because you need to add a bit to the high register and one bit is 2^0 = 1.

A couple of the functions used are:
addu $lowReg, $lowReg, $multiplicandReg Add the shifted multiplicand to the low register
sll $multiplicandReg, 1 This shifts the multiplicand left by 1 bit
and $t0, $multiplier, 1 Check if the least significant bit is a 1
srl $multiplier, 1 Once you've checked if it's a 1 or 0 you can shift that bit off the register

There are a couple of others but those are the main ones that should allow for 2 numbers that are pretty small to easily multiply.

 

[rcgldr]

when the result register actually has a carry bit.

This gets back to the issue that the MIPS doesn't have a carry (or borrow if subtract) bit. You need to use the method I mentioned in my first reply to work around this.

If you store large integers using only 16 bits of each 32 bit register, you can use the multiply instruction to do multiplies. The method is similar to doing long hand multiplication. After a multiply step to produce a set of intermediate product terms, the upper 16 bits of a low order word get added to the lower 16 bits of the next higher order word (then those upper 16 bits in the low order word are zeroed out), looping through all the words used to hold the product.