MIPS Multiplication of More Than 32 Bits

Question

For an assignment, I need to develop a recursive algorithm were given an input string I print out the unsigned decimal integer corresponding to the base-30 number represented by the string. (a-10;b-11;...) For example:

Given input:

"AAAAAAAAAAaaaaaaaaaa"

Expected Output:

120233944862068965517241379310

Additional instructions: Max 20 characters allowed in the input. The memory address of the input string is passed into the subprogram via a register, and the decimal integer is returned via the stack (as a register is probably not enough to hold the result).

I understand the recursion part of MIPS, but registers can only hold 32 bits. So we simply cannot store the result in a register because it is larger. What is an effective way to break the problem down where I can do the calculation by multiplying?

Ex. 'A'(10)*30^19 + 'A'(10)*30^18 + ... + 'a'(10)*30^0

Without just giving me the code as this is an assignment but if someone can just point me in the right direction that would be great!

`total = total*base + digit`. base 30 is `32 - 2` so you could do extended-precision left shifts by 2 different counts and subtract. That would get you a large *binary* integer. But it seems you want a *decimal* output? And that you want to convert *from* base 30, not *to*. Your example problem is the opposite of what your first paragraph states. — Peter Cordes, Feb 22 '20 at 03:49
I am guessing it was fixed in the edit, it makes more sense now. — old_timer, Feb 22 '20 at 06:59

score 3 · Accepted Answer · edited Jul 19 '21 at 22:07

You can have numbers as large as you have registers or memory, think about grade school multiplication, and think about how base two simplifies it.

     abcdef
*    111101
============
     abcdef
    000000
   abcdef
  abcdef
 abcdef
abcdef

but what if I only have 2 bit registers?

You would do this kind of thing:

        ab cd ef
      0 00 00 0
     ab cd ef
   a bc de f
  ab cd ef
a bc de f
===============

which you could take two rows at a time.

Another way to think of it from grade-school hex numbers I want to say multiply 16 bit numbers but I only have a 8 bit * 8 bit = 16 bit multiply instruction:

abcd * 1234 =
((ab*(2^8))+(cd*(2^0))) * ((12*(2^8))+(34*(2^0)) = 
((ab*x)+(cd*y)) * ((12*x)+(34*y) = 
ab*12*x*x + ab*34*x*y + cd*12*x*y + cd*34*y*y =

x and y are just powers of two, but more than that such they put results on 8 or 16 or more powers of 8 bit boundaries. The numbers can now be done with 8 bit * 8 bit = 16 bit multiply or a 16 bit * 16 bit = 16 bit multiply with the upper bits padded. then you keep track of who lands where, there are some additions with some carries that add to the next group.

That is how you can use what you know from school, to cascade this stuff with registers/instructions you have.

So you could build a large multiplier and I assume you know how to cascade addition or can figure it out in a similar way, and "just" use that.

But your problem is as you stated. (10)*30^19 + (10)*30^18 and so on.

#include <stdio.h>
int main ( void )
{
    unsigned int ra;
    unsigned int rb;
    unsigned int rc;

    for(ra=1;ra<6;ra++)
    {
        rc=1;
        for(rb=0;rb<ra;rb++)
        {
            rc*=30;
        }
        printf("%2u 0x%08X %u\n",ra,rc,rc);
    }
    return(0);
}

 1 0x0000001E 30
 2 0x00000384 900
 3 0x00006978 27000
 4 0x000C5C10 810000
 5 0x0172C9E0 24300000

30 is 352. it is not going to look pretty at all in binary, it won't look bad in decimal. maybe there is a trick there.

abc = 10*30*30 + 11*30 + 12*0
9000 + 330 + 12
9312

im not seeing it yet.

but if you think about that 3,5,2

in binary x3 is (x<<1)+x; x5 is (x<<2)+x and x*2 = x<<1;

if decimal (base 10) 1234

x = 1;
for each digit that remains in the string
x = x * 10; //shift left one number place
x = x + 2; //next digit
...

converting base 10 to binary

x = 1;
x = (x<<3)+(x<<1); //x = x * 10;
x = x + 2;
x = (x<<3)+(x<<1);
x = x + 3;
x = (x<<3)+(x<<1);
x = x + 4;

or

x = 0;
x = (x<<3)+(x<<1);
x = 1;
x = (x<<3)+(x<<1);
x = x + 2;
x = (x<<3)+(x<<1);
x = x + 3;
x = (x<<3)+(x<<1);
x = x + 4;

or

x = 0;
y = x<<3;
x = y + x<<1;
x = x + 1;
y = x<<3;
x = y + x<<1;
x = x + 2;
y = x<<3;
x = y + x<<1;
x = x + 3;
y = x<<3;
x = y + x<<1;
x = x + 4;

Something that is easy to make a loop out of making it base 30 to binary instead of base 10 to binary as shown. Shifting small numbers is easy to cascade across as many registers or memory locations as you have room for. The addition steps can only carry out one bit so that is easy to cascade across as many registers/memory locations. So a base 10 to base 2 longer-than-you-have-bits-in-a-register is not difficult. Now turning that quite long binary number into base 10 to print it out, yeah that is a new problem.

Maybe the trick here is a pseudo bcd type approach, one nibble per decimal digit and you are doing this kind of thing:

 1 0x0000001E 30
 2 0x00000384 900
 3 0x00006978 27000
 4 0x000C5C10 810000
 5 0x0172C9E0 24300000

"abc" 10, 11, 12

x = 0x0
x = x * 0x30 = (x<<5) + (x << 4); //hmmm is that right?
x = x + 0x10;
...

but for all of this addition you have to go through right to left and cover the bcd overflows so 0x1A becomes 0x20 because 0xA is larger than 9 by one so that is a carry of one into the next nibble. That gets ugly, but what if each BCD digit were 8 bits?

That's the path I am thinking, if you were to build yourself a multi-register large multiplier how many registers/memory locations would it take to handle the 30^19th power? That's how big it would have to be but then if you built it then it would be easy-ish to use. To get it to binary. Now you are going to build a large divider to get it from binary to base 10?

That is doable, you do it long division style 10 is 0b1010 you are really walking a 101 under the bits for each bit you get a 0 or a 1 its long division which you can program in a loop pulling off one bit from the numerator at a time starting from the msbit and comparing that accumulation of bits with 0b101 or 0b1010 it will be less than 2 times 10 so the result is accumulating 1's or 0's and like long division you are subtracting out either 0 times 10 or 1 times 10 as you go.

0x1D / 10

11101

we pull down one of the numerator bits at a time just like long division in an accumulator if you will and compare that to the denominator

1 compared to 1010 is 0 remainder 1 next bit 11 compared to 1010 is 0 remainder 11 111 compared to 1010 is 0 remainder 111 1110 compared to 1010 is 1 remainder 100 1001 compared to 1010 is 0 remainder 1001

The result is 00010 or 2, 0x1D / 10 = 29 / 10 = 2 easy to make an accumulator only needs to be 4 bits easy to walk one bit at a time through an infinite number of 32 bit registers or memory locations. but you have to do this a zillion times

1234 decimal = 0x4D2

0x4D2 / 10 = 0x7B remainder 4
0x7B / 10 = 0xC remainder 3
0xC / 10 = 0x1 remainder 2
0x1 / 10 = 0 remainder 1

So we are done, result 1234 decimal.

You are starting with 0x4D2 and getting 0x7B and 4 out of it, but instead of a small number of bits this is dozens/hundreds of bits.

brute force if you can make the multiplier in binary cascade for the number of 32 bit words you need with no mistakes and then the division is not that hard to code. you can make this work using multiplication.

30^20 = 3.4..*10^29

My brain isn't quite figuring the number of bits/words you need to store this number.

Anyway, yes you can cascade a 32 bit * 32 bit = 32 bit (16 bits at a time) or 32 bit * 32 bit = 64 bit (32 bits at a time) multiplier as wide as you have memory for (going to run out of registers quickly use registers for the multiplies and the additions and add with carrys, use memory to hold the actual numbers). ending up with a base 2 result. Then you can make a long division algorithm and churn through that until the numerator is 0. Is multiply required for the assignment?

being sloppy using an array of bytes each representing a bcd number, I took the string converted it to base 10, for each digit in the input string I multiplied my "accumulator" by 10 then times 3. added in the new digit and repeated until there were no digits. then my "accumulator" had the result in base 10 no division required. no multiplies used. all told there were a handful or so of loops a few comparisons, one loop I cut and pasted could have made a function out of it and called it twice. took a few minutes all told to write in C using syntax that can relatively easily translate to asm — old_timer, Feb 22 '20 at 08:55
Thanks @old_timer! Multiplication isn't required at all that was just the way I thought of doing it at first. The first iteration of the assignment only allowed MAX 4 characters in the input which made it pretty simple to store that result in a register. — JabariD, Feb 22 '20 at 13:50

MIPS Multiplication of More Than 32 Bits

1 Answers1