How many digits will be after converting from one numeral system to another

Question

The main question: How many digits?

Let me explain. I have a number in binary system: 11000000 and in decimal is 192.

After converting to decimal, how many digits it will have (in dicimal)? In my example, it's 3 digits. But, it isn't a problem. I've searched over internet and found one algorithm for integral part and one for fractional part. I'm not quite understand them, but (I think) they works.

When converting from binary to octal, it's more easy: each 3 bits give you 1 digit in octal. Same for hex: each 4 bits = 1 hex digit.

But, I'm very curious, what to do, if I have a number in P numeral system and want to convert it to the Q numeral system? I know how to do it (I think, I know :)), but, 1st of all, I want to know how many digits in Q system it will take (u no, I must preallocate space).

Answer 1

The keyword here is "logarithm", here are some suggestive links:

http://www.adug.org.au/MathsCorner/MathsCornerLogs2.htm

http://staff.spd.dcu.ie/johnbcos/download/Fermat%20material/Fermat_Record_Number/HOW_MANY.html

Answer 2

Writing n in base b takes ceiling(log base b (n)) digits.

The ratio you noticed (octal/binary) is log base 8 (n) / log base 2 (n) = 3.

(From memory, will it stick?)

Answer 3

look at the logarithms base P and base Q. Round down to nearest integer.

The logarithm base P can be computed using your favorite base (10 or e): log_P(x) = log_10(x)/log_10(P)

Answer 4

If you have a number that's X digits long in base B, then the maximum value that can be represented is B^X - 1. So if you want to know how many digits it might take in base C, then you have to find the number Y that C^Y - 1 is at least as big as B^X - 1. The way to do that is to take the logarithm in base C of B^X-1. And since the logarithm (log) of a number in base C is the same as the natural log (ln) of that number divided by the natural log of C, that becomes:

Y = ln((B^X)-1) / ln(C) + 1

and since ln(B^X) is X * ln(B), and that's probably faster to calculate than ln(B^X-1) and close enough to the right answer, rewrite that as

Y = X * ln(B) / ln(C) + 1

Covert that to your favourite language. Because we dropped the "-1", we might end up with one digit more than you need in some cases. But even better, you can pre-calculate ln(B)/ln(C) and just multiply it by new "X"s and the length of the number you are trying to convert changes.

Answer 5

Calculating the number of digit can be done using the formulas given by the other answers, however, it might actually be faster to allocate a buffer of maximum size first and then return the relevant part of that buffer instead of calculating a logarithm.

Note that the worst case for the buffer size happens when you convert to binary, which gives you a buffer size of 32 characters for 32-bit integers.

Converting a number to an arbitrary base could be done using the C# function below (The code would look very similar in other languages like C or Java):

public static string IntToString(int value, char[] baseChars)
{
    // 32 is the worst cast buffer size for base 2 and int.MaxValue
    int i = 32;
    char[] buffer = new char[i];
    int targetBase= baseChars.Length;

    do
    {
        buffer[--i] = baseChars[value % targetBase];
        value = value / targetBase;
    }
    while (value > 0);

    char[] result = new char[32 - i];
    Array.Copy(buffer, i, result, 0, 32 - i);

    return new string(result);
}

Answer 6

There was an error in my previous answer: look at the comment by Ben Schwehn. Sorry for the confusion, I found and explain the error I made in my previous answer below.

Please use the answer provided by Paul Tomblin. (rewritten to use P, Q and n)

Y = ln(P^n) / ln(Q)
Y = n * ln(P) / ln(Q)

So Y (rounded up) is the number of characters you need in system Q to express the highest number you can encode in n characters in system P.

I have no answer (that wouldn't convert the number already and take up that many space in a temporary variable) to get the bare minimum for a given number 1000(bin) = 8(dec) while you would reserve 2 decimal positions using this formula.

If a temporary memory usage isn't a problem, you might cheat and use (Python):

len(str(int(otherBaseStr,P)))

This will give you the number of decimals needed to convert a number in base P, cast as a string (otherBaseStr), into decimals.

---

Old WRONG answer:

If you have a number in P numeral system of length n Then you can calculate the highest number that is possible in n characters:

P^(n-1)

To express this highest number in number system Q you need to use logarithms (because they are the inverse to exponentiation):

log((P^(n-1))/log(Q)
(n-1)*log(P) / log(Q)

For example 11000000 in binary is 8 characters. To get it in Decimal you would need:

(8-1)*log(2) / log(10) = 2.1 digits (round up to 3)

Reason it was wrong:

The highest number that is possible in n characters is

(P^n) - 1

not

P^(n-1)

Answer 7

You need to compute the length of the fractional part separately.

For binary to decimal, there are as many decimal digits as there are bits. For example, binary 0.11001101001001 is decimal 0.80133056640625, both 14 digits after the radix point.

For decimal to binary, there are two cases. If the decimal fraction is dyadic, then there are as many bits as decimal digits (same as for binary to decimal above). If the fraction is not dyadic, then the number of bits is infinite.

(You can use my decimal/binary converter to experiment with this.)