Converting between number systems

[chaoseverlasting]

I'm writing a program to convert between the different number systems (from decimal to any base), I know what the general algorithm is and how to implement it. The problem I am facing is, that I don't know how do decide the number of digits in the converted number.

For example, if I were to convert 10 from decimal to binary, I would get 1010, but the number of digits has changed from 2 to 4. How do you decide the number of digits in the new number (1010 in this case).

I know that roughly, if youre changing to a base greater than 10, the number of digits should decrease, and if converting to a base lesser than 10, the digits should increase, but don't know by how much.

 

[Defennder]

There isn't any general algorithm. I had this for a lab assignment one and I made use of a different algorithm from the one the lab TAs were teaching. My algorithm converted the decimal base from front to back while theirs did the reverse. You should describe how your algorithm is supposed to work before we can help.

 

[MeJennifer]

I don't know how do decide the number of digits in the converted number.

Think of a simple formula that can determine the tallest number a given number of digits can hold in any base. For instance for 4 digits in the 10-based system it is 10 * 10 * 10 * 10 - 1 for the binary system it would be 2 * 2 * 2 * 2- 1.

 

[Borek]

Think how log_base(number) relates to the number of digits.

 

[chaoseverlasting]

There isn't any general algorithm. I had this for a lab assignment one and I made use of a different algorithm from the one the lab TAs were teaching. My algorithm converted the decimal base from front to back while theirs did the reverse. You should describe how your algorithm is supposed to work before we can help.

Im doing it the only way I know how, whatever number need to be converted is divided repeatedly by the base and the remainders are collected. The collected remainders in the reverse order is the number.

Im collecting the remainders in a dynamic array, and I need to know the size of the converted number to define the size of the array.

Think how log_base(number) relates to the number of digits.

If we use a base 10 number and find log₁₀(number) for it, then because that number can be expressed in powers of 10, then [log10[/number](number)] (where[...] is the greatest integer function) will give us the number of digits -1 because whatever the number, without the powers of 10 its value should always be lesser than 1.
Carrying this forward to other bases, if I convert to binary, then log₂(number}₂ should give me number of digits of binary -1 right?

The only problem with this is that I need to know the binary number to find its length and I can't initialize the array. How can I find out the length of the number before conversion?

Think of a simple formula that can determine the tallest number a given number of digits can hold in any base. For instance for 4 digits in the 10-based system it is 10 * 10 * 10 * 10 - 1 for the binary system it would be 2 * 2 * 2 * 2- 1.

Why does the -1 come in? I mean I get that 10⁴ would be 5 digits, but is there a more formal reason for it?

 

[Borek]

The only problem with this is that I need to know the binary number to find its length and I can't initialize the array. How can I find out the length of the number before conversion?

Number is a number, and its log is its log, doesn't matter if it is decimal, hexadecimal or something else.

Do you know how to convert between logarithms of different bases? Pretty simple operation.

 

[chaoseverlasting]

Number is a number, and its log is its log, doesn't matter if it is decimal, hexadecimal or something else.

Do you know how to convert between logarithms of different bases? Pretty simple operation.

Yeah, that's not what I meant. What I mean is, that when I am converting between base 10 and any other base, how can I find the length of the number in the other base? Eg, 10 from decimal to binary is 1010, and the length in binary is 4. Before converting, how can I find the length in binary?

The log method will only work after I've found the number out (ie, log₂1010 =3.something), but I can't use this before converting 10. Thats what I need to do.

 

[HallsofIvy]

Yeah, that's not what I meant. What I mean is, that when I am converting between base 10 and any other base, how can I find the length of the number in the other base? Eg, 10 from decimal to binary is 1010, and the length in binary is 4. Before converting, how can I find the length in binary?

The log method will only work after I've found the number out (ie, log₂1010 =3.something), but I can't use this before converting 10. Thats what I need to do.

No! That's not what he's saying at all! 16₁₀= 10000₂ because 16= 2⁴. It has 5 bits because it is 2⁴ and so is a 1 followed by 4 0s. 17₁₀= 10001₂ because 17= 2⁴+ 1. It has 5 bits because it is 1 (less than 2) added to 2⁴. Or, more consisely, 16, in base 2 has 5 bits because log₂(16)+ 1= 4+1 (the "1" is added for the non-zero bit) and 17, in base 2, also has 5 bits because log₂(17)= log₁₀(17)/log₁₀(2)= 4.087... has integer part 4 and 4+ 1= 5.

In general, the number X, in base 10, converted to base a, has log₁₀(X)/log₁₀(a)+ 1 "digits".


For example, the number 1232311, base 10, converted to base 16, has 6 "digits" because log₁₀(1232311)/log₁₀(16)= 5.897... has integer part 5; 6= 5+1. And, in fact, it is easy to show that 1232311₁₀= 12CDB7₁₆, with 6 "digits".

 

[chaoseverlasting]

No! That's not what he's saying at all! 16₁₀= 10000₂ because 16= 2⁴. It has 5 bits because it is 2⁴ and so is a 1 followed by 4 0s. 17₁₀= 10001₂ because 17= 2⁴+ 1. It has 5 bits because it is 1 (less than 2) added to 2⁴. Or, more consisely, 16, in base 2 has 5 bits because log₂(16)+ 1= 4+1 (the "1" is added for the non-zero bit) and 17, in base 2, also has 5 bits because log₂(17)= log₁₀(17)/log₁₀(2)= 4.087... has integer part 4 and 4+ 1= 5.

In general, the number X, in base 10, converted to base a, has log₁₀(X)/log₁₀(a)+ 1 "digits". For example, the number 1232311, base 10, converted to base 16, has 6 "digits" because log₁₀(1232311)/log₁₀(16)= 5.897... has integer part 5; 6= 5+1. And, in fact, it is easy to show that 1232311₁₀= 12CDB7₁₆, with 6 "digits".

Thank you so much! I was just running around in circles trying to figure that out! That brilliantly explains it!

And thank you Borek and everyone else for helping me along!

 

[chaoseverlasting]

I can't figure out what I am doing wrong. Could someone please tell me where I am going wrong? Here's the code:

//N-base system conversion program

#include <iostream>
#include <cmath>

using namespace std;

void convert(int , int, int, int*);    //convert(number, base, length, result)

int len=0, i;

int main()
{
    int num, base, *r;
    
    cout<<"\nEnter a number: ";
    cin>>num;
    cout<<"\nEnter base: ";
    cin>>base;
    
    len=(int)log10(num)/log10(base)+1;       //Number of digits of the converted number
    
    r=new int [len];
    
    convert(num, base, len, r);
    
    cout<<endl;
    
    for(i=0; i<len; i++)
    cout<<*(r+i);

    delete [] r;
    
    return 0;
}

void convert(int n, int b, int len, int* res)
{
     for(i=0; i<len; i++)
     {
              *(res+len-i)=n%b;
              n/=b;
     }
}

 

[chaoseverlasting]

Problem solved. Forgot to subtract 1 in statement *(res+len-i). Should be *(res+len-i-1). Stupid mistake.

 

[Ben Niehoff]

Or you can write

for (i = len - 1; i >= 0; i--)

There's no rule that says your FOR loops must count up.

 

[Borek]

Are you aware of

char *itoa( int value, char *string, int radix );

which does exactly what you need? Could be you were asked to write it on your own, but there is already a library version.

 

[mgb_phys]

Think how log_base(number)

Is there an obvious way of calculating log_base(number) from log₁₀(number) for any base?

 

[Borek]

Is there an obvious way of calculating log_base(number) from log₁₀(number) for any base?

We have known

a = \log_bx

and we need

c = \log_dx

obviously

b^a = x

so

c = \log_db^a = a*\log_db

but you already know a, so you just multiply by log_db and you are ready

 

[mgb_phys]

obviously

b^a = x

Only "obviously" if you have itthe right way round!
Somehow I managed to get a^b = x !

thanks - I'm sure that will come in useful one day, not sure when.

 

[Borek]

It was much more obvious 30 years ago, when calculators were much more rare then now. Everyone knew how to convert from ln to log₁₀ - by multipliying by 2.303!

 

[chaoseverlasting]

Are you aware of

char *itoa( int value, char *string, int radix );

which does exactly what you need? Could be you were asked to write it on your own, but there is already a library version.

No actually! This wasnt homework, it was something I wanted to do because I need to use it in another one of my programs. I didnt know there was already something written for it! How do you use that function though?

 

[Borek]

#include <stdio.h>
#include <stdlib.h>

const int iNumber = 123456789;

int main()
{
	char sz[33]; // will be enough for any 32-bit integer
	int iRadix;

	printf("Number %i(dec) is:\n",iNumber);

	for (iRadix = 2;iRadix != 33;iRadix++)
	{
		itoa(iNumber,sz,iRadix);
		printf("base: %2i -> %32s\n",iRadix,sz);
	}

	return 0;
}

Output:

Number 123456789(dec) is:
base:  2 ->      111010110111100110100010101
base:  3 ->                22121022020212200
base:  4 ->                   13112330310111
base:  5 ->                     223101104124
base:  6 ->                      20130035113
base:  7 ->                       3026236221
base:  8 ->                        726746425
base:  9 ->                        277266780
base: 10 ->                        123456789
base: 11 ->                         63762a05
base: 12 ->                         35418a99
base: 13 ->                         1c767471
base: 14 ->                         12579781
base: 15 ->                          ac89bc9
base: 16 ->                          75bcd15
base: 17 ->                          51g2a21
base: 18 ->                          3b60f89
base: 19 ->                          2bg64ae
base: 20 ->                          1ibc1j9
base: 21 ->                          194gh7f
base: 22 ->                          11l0805
base: 23 ->                           j43jfb
base: 24 ->                           fc2egl
base: 25 ->                           cg15le
base: 26 ->                           aa44a1
base: 27 ->                           8g86ni
base: 28 ->                           74nqb1
base: 29 ->                           60fshj
base: 30 ->                           52ce69
base: 31 ->                           49l302
base: 32 ->                           3lnj8l

Honestly, I don't remember how digits over F are assigned. And it works only for numbers lesser then INT_MAX.

Tried under Visual C.