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!
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?