macOS *ugh* Being Forced To Use Arrays

[bobber205]

For my programming class, I have to make a app that converts whatever base into whatever else base.

Not hard. At all.

The only thing I'm wrestling over before I start actually coding is how I should use arrays.
I was just going to make a string and store each new 0-9 or A-Z character in there. Do you think he's wanting us to use an array to store the result?

I was thinking more along the lines of having an array that holds the characters A-Z for numbers 10-36 and having the function access that array and then return the appropriate character by a value passed to that function.

So.. what do you guys think?

 

[darkwing]

For my programming class, I have to make a app that converts whatever base into whatever else base.

Not hard. At all.

The only thing I'm wrestling over before I start actually coding is how I should use arrays.
I was just going to make a string and store each new 0-9 or A-Z character in there. Do you think he's wanting us to use an array to store the result?

I was thinking more along the lines of having an array that holds the characters A-Z for numbers 10-36 and having the function access that array and then return the appropriate character by a value passed to that function.

So.. what do you guys think?

I like your second approach... but when you say "whatever base into whatever other base" does that mean that you only support up to Z? Hex is A-F of course, but that's established for base 16. Would base 15 only go to E? It just seems odd.

For printing hex, for example, I like to store 0-9, A-F in an array and then I can go through a nibble at a time and print that character. Perhaps you can type up the assignment?

 

[iMeowbot]

I was thinking more along the lines of having an array that holds the characters A-Z for numbers 10-36 and having the function access that array and then return the appropriate character by a value passed to that function.

That's along the line of the usual approach. You may find this easier if you include 0-9.

 

[bobber205]

0-9 stay the same.

10-36 are A-Z.

I'm just hoping he's not wanting us to do the final answer in an array.

*launches word and waits and waits*

Purpose: For this lab you will write a program to convert numbers to different bases. For example:

FF16 = 25510 = 3778 = 111111112 = C321 = 73 36

Your program will prompt the user to enter a “number” and the base of the number. You will then ask what base to convert the number to. I expect you to handle bases 2 – 36.

Stipulations:
1) The program must continue until the user chooses to quit.
2) If the user enters a base outside the range stated above, display an error message and make them re-enter the base.
3) If the number doesn’t match the base they typed in, display an error message and have them re-enter all of the information again. (ie. The character A is invalid for a base 10 number.)
4) The number displayed to the user should be displayed in uppercase.
5) You must use functions and arrays.
6) Be sure your output is self-documenting. For example:
FF (base 16) = 255 (base 10).

Hints:
1) The maximum digit that can be in a number is one less than its base. For example: 7 is the maximum digit in a base 8 number, 1 is the maximum digit in a base 2 number.
2) Convert all numbers to base 10 first and then convert them to the desired base.

Due Date: Friday, February 23, 2007.
WARNING: Get started early!

Lol. We got this assignment a few days ago. I'll be done with it tomorrow.


Want to know something funny? On our first test, right before we learned about for loops, I was marked off on that test because I said

cin << name1 << name2;

was a legitimate line of code. WTF. It is and it was in our reading for that week. The reason he made it "wrong" was because he wanted us to us some gay for loop to get 4 values.

Lol.

 

[darkwing]

The best thing to do, imho, is to convert all numbers in any base to base 10, and go from there. This provides a good use for arrays at the end.

I'm going to assume that you know how to convert to base 10, so a good use for an array would be when going from base 10 to another number. As you move through the number with loops, division, and modulus, you can print the proper character from an array like:

static const char array[] = { '0', '1', '2', ..., '9', 'A', 'B', ... 'Z' };

then, as you convert from base 10 you have the character for each digit in this array. Then, store that in another array because you will need to print the results backwards. (usually base 10 to base x routines produce the lower digits first) Or, use a mehod that produces the larger numbers first.

Just a thought.

 

[bobber205]

I guess I will have to use an array to loop backwards in.

oh well. It's easier than making everything a string and reversing it (like how I did this for base-2 in java).

 

[bronxbomber92]

How would you from base 16 to another base? I'v done base 2 to base 10, and base 10 to, well, base 2 and to roman numerals p)... Hexadecimal seems, different...

 

[iMeowbot]

How would you from base 16 to another base? I'v done base 2 to base 10, and base 10 to, well, base 2 and to roman numerals p)... Hexadecimal seems, different...

You already know how to do this (in decimal). Remember when you were taught that 345 is 300 + 40 + 5 ? It works the same way for any other base, the only thing that changes is the size of the number you can fit into each digit.

 

[toddburch]

As an FYI, when bobber205 is done with his assignment, I'll post a Ruby script I wrote about a month ago that does base to base conversions. I find it interesting to see and compare the different techniques used to tackle the same problem.

Todd

 

[bobber205]

That's a good idea. I'll be sure to post everything here when I'm done.

 

[jeremy.king]

It's easier than making everything a string and reversing it (like how I did this for base-2 in java).

public static String convertToBase(int n, int base) {
  return Integer.toString(n, base);
}

 

[MarkCollette]

If you have to use arrays, then you could make a 2d array, where the first index is the base, and the second index is for every ASCII character, mapping to its base 10 value. Invalid values would map to a sentinel value (some arbitrary constant where 36 < SENTINEL <= 255). Hell, even if your lookup tables were 16 bit char arrays, we're only talking about 36 * 64KB memory overhead.

I personally wouldn't use a lookup table for such a trivial calculation, but it might demonstrate knowledge of arrays quite well.

 

[bobber205]

Is there an efficient way to convert chars to an integer? or should I just make a function that does this with 10 switch cases?

 

[MarkCollette]

Do you means chars like '0' through '9' ?

char typedInChar = '5';
int numericValue = typedInChar - '0';

Or 'A' through 'Z' ?

char typedInChar = 'M';
int numericValue = typedInChar - 'A' + 10;

You don't have to cast when converting from a char to an int, since the language already defines what happens. In this case, both typedInChar and 'A' are chars, so the subtraction involves no conversion, but 10 is an int, so the addition will promoted the result of the previous subtraction to an int. There's no more conversions, because the result of the addition is an int, and so is numericValue.

When converting from a char to an int, which are both signed in Java/C/C++, there is a possible sign extension. Basically chars are usually less bits than ints, so the extra bits of the int are made up by taking the single highest bit of the char and duplicating it. Now, chars are a weird beast, since they're signed numeric values, but are interpretted as characters, where sign doesn't really apply. So when calculating the integral value of these arbitrary based characters, you probably don't want funky Unicode characters to come across as negative valued integers. Luckily, you know that you max base is 36, and its max value is 35, which is a positive value, so should not present an issue for sign extension. You should probably check the input value against the max value for whichever base before you do any calculations with it. So, if it passes the test, then you're golden.

 

[ChrisA]

Is there an efficient way to convert chars to an integer? or should I just make a function that does this with 10 switch cases?

Some "Pseudo C". Can anyone do this any shorter? Beats doing 36 switch cases


int myfunct(char xx) {
char a[]=0123456789abcdefghi....;
if(num = strnchr(a, xx, base) ){
return (int)(num - &(xx[0]));
else
print error "invalid character"
return -1;

 

[Palad1]

We could easily make it a tad longer with array bounds checking

 

[darkwing]

We could easily make it a tad longer with array bounds checking

This can be solved by design. One of the advantages to what I suggested by converting things to base 10.

Mark, I thought about what you said but then decided it would be too much to type and kind of beyond the scope of the assignment to write a program (or script) to generate a source file for you. Besides, you should have a 3-dim array. array[base][desired_conversion_base][value] and then move through one digit at a time.

This is getting too crazy.

 

[MarkCollette]

darkwing, I envisionned it as the two stage conversion, of:

1. Convert from arbitrary input base to summable ints components, using the two dimensional array, instead of multiplication

2. Convert from int to arbitrary output base, using calculation

Since the input range of each char is limited, and thus could use arrays, but the intermediate int/long could be quite large, so the output is bounded so high that an array in stage two in not useful.

 

[ChrisA]

We could easily make it a tad longer with array bounds checking

"strnchr" does the array bound check for us.

Notice "strnchr" vs. "strchr". It will stop scanning the string after looking at "base" characters and return a NULL if not found. The NULL is used to indicate back to the user that he typed an invalid character.

 

[MarkCollette]

This brings to mind another question: what is the maximum value being converted?

Let's say, as an example, that the input is in hexadecimal, and the typed in value is FFFF. Then the conversion could be done with an int. But, if the input value were FFFFFFFFFFFFFFFFFFFFFFFF, then a completely different type of solution would be required.

 

[darkwing]

darkwing, I envisionned it as the two stage conversion, of:

1. Convert from arbitrary input base to summable ints components, using the two dimensional array, instead of multiplication

2. Convert from int to arbitrary output base, using calculation

Since the input range of each char is limited, and thus could use arrays, but the intermediate int/long could be quite large, so the output is bounded so high that an array in stage two in not useful.

There is bounding if you take the approach of one character at a time. As you move through each "digit" in the base, you have a bound and a value as long as you apply some multiple to it. Of course this won't be as fast as having vast arrays for every possible conversion, but it is a good compromise. This is what I had in mind.

 

[iMeowbot]

"strnchr" does the array bound check for us.

That's not a standard function, so you still need to write one and do some checking.

 

[MarkCollette]

There is bounding if you take the approach of one character at a time. As you move through each "digit" in the base, you have a bound and a value as long as you apply some multiple to it. Of course this won't be as fast as having vast arrays for every possible conversion, but it is a good compromise. This is what I had in mind.

Oh, you mean having an output array like:

char[] output = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', ... , 'Z' };

And when you calculate each output component in the output base, you then use it as an index into this table? Like if the value was 227 (base10) and the output was in base 14, so we extract out component values of: 196 + 28 + 3 (base 10) or 1x14^2 + 2x14^1 + 3x14^0. So we feed in 1,2,3 into the table, and get out '1', '2', '3'?

Or do you mean that we have:

char output[NUM_BASES][NUM_POWERS_OF_BASE][VALUES] ?

Because we'd still have to worry about the size of NUM_POWERS_OF_BASE, which would be tied to the output string length.

 

[MarkCollette]

Haven't verified if it compiles or works or whatever.

final int MAX_BASE = 36;
final int NUM_CHARS = 65536;
final int SENTINEL_VALUE = 255;

int convertInputToComponentValue[MAX_BASE][];
for(int base = 2; base < MAX_BASE; base++) {
    // Make it large enough to take any user input char
    convertInputToComponentValue[base] = new int[NUM_CHARS];
    // Default every input as an invalid character
    for(int i = 0; i < NUM_CHARS; i++)
    	convertInputToComponentValue[base][i] = SENTINEL_VALUE;
    // Map the relevant parts of '0'-'9', in the current base, to their integral value
    // Eg; For base 2, only {'0' -> 0, '1' -> 1} are relevant
    for(int input = 0; input <= Math.min(9,base-1); input++) {
    	int actualCharIndex = input + '0';
    	convertInputToComponentValue[base][actualCharIndex] = input;
    }
    // Map the relevant parts of 'A'-'Z', in the current base, to their integral value
    // Eg; For base 13, only {'A' -> 10, 'B' -> 11, 'C' -> 12} are relevant
    for(int input = 10; input < Math.min(MAX_BASE,base); input++) {
    	int actualCharIndex = input - 10 + 'A';
    	convertInputToComponentValue[base][actualCharIndex] = input;
    	
    	// Hell, why not cover lower case as well
    	actualCharIndex = input - 10 + 'a';
    	convertInputToComponentValue[base][actualCharIndex] = input;
    }
}

char[] convertComponentValueToOutput = new char[MAX_BASE];
for(int i = 0; i < 10; i++)
    convertComponentValueToOutput[i] = i + '0';
for(int i = 10; i < MAX_BASE; i++)
    convertComponentValueToOutput[i] = i - 10 + 'A';

// Now take an inputted value, and convert each char into component values
int inputBase = 5;
String inputString = "2130";

int totalValue = 0;
for(int i = 0; i < inputString.length(); i++) {
    int componentValue = convertInputToComponentValue[inputBase][inputString.charAt(i)];
    if( componentValue == SENTINEL_VALUE )
    	System.out.println("ARGH, the hills be swarming with orcs!");
    totalValue *= inputBase;
    totalValue += componentValue;
}

// In this case, each componentValue was: 2,1,3,0 so totalValue was: 2,11,58,_290_

int outputBase = 7;
StringBuffer reversedOutputString = new StringBuffer();

// Now output the value, as discrete component characters
do {
    int componentValue = totalValue % outputBase;
    totalValue -= componentValue;
    totalValue /= outputBase;
    
    char componentChar = convertComponentValueToOutput[componentValue];
    reversedOutputString.add( componentChar );
} while(totalValue != 0);

// In this case, each componentValue was: 3, 6, 5
// So the proper output is "563"
// Double-check 5x7^2 + 6x7^1 + 3x7^0 = 245 + 42 + 3 = 290

String outputString = reversedOutputString.reverse.toString();

 

[MarkCollette]

And now, for the easier to read non-array version. Same disclaimers.

// Now take an inputted value, and convert each char into component values
int inputBase = 5;
String inputString = "2130";

int totalValue = 0;
for(int i = 0; i < inputString.length(); i++) {
    int componentValue = 0;
    
    char curr = inputString.charAt(i);
    if( curr >= '0' && curr <= '9' )
    	componentValue = curr - '0';
    else if( curr >= 'A' && curr <= 'Z' )
    	componentValue = curr - 'A';
    else if( curr >= 'a' && curr <= 'z' )
    	componentValue = curr - 'a';
    else
    	System.out.println("ARGH, the hills be swarming with orcs!");
    if( componentValue >= inputBase )
    	System.out.println("ARGH, the hills be swarming with orcs!");
    
    totalValue *= inputBase;
    totalValue += componentValue;
}

// In this case, each componentValue was: 2,1,3,0 so totalValue was: 2,11,58,_290_

int outputBase = 7;
StringBuffer reversedOutputString = new StringBuffer();

// Now output the value, as discrete component characters
do {
    int componentValue = totalValue % outputBase;
    totalValue -= componentValue;
    totalValue /= outputBase;
    
    char componentChar = componentValue + (componentValue <= 9 ? '0' : 'A');
    reversedOutputString.add( componentChar );
} while(totalValue != 0);

// In this case, each componentValue was: 3, 6, 5
// So the proper output is "563"
// Double-check 5x7^2 + 6x7^1 + 3x7^0 = 245 + 42 + 3 = 290

String outputString = reversedOutputString.reverse.toString();