How to count the number of digits in different databases?

Question

I work with numbers in different bases (base-10, base-8, base-16, etc.). I am trying to count the number of characters in each number.

Example

Number: ABCDEF

Number of digits: 6

I know about a method based on logarithms, but I have to face some problems.

• This Python script displays that he was unable to correctly calculate the number of digits in 3996 numbers out of 1,000,000.

• I think a method that uses logarithms can be quite slow

References:

• This C program should be very slow (what if I have a very large number?). It also cannot process numbers in different bases (e.g. base-16).

• Not cheating on this , since there the OP only asked about base-10

---

Edit: Of course, I can calculate the length of the string, but what interests me the most is if you can perform the calculation without a legend for the string. I would like to know an algorithm that could help do this, knowing only the source base and the base for the conversion.

Edit2: the source base is base-10, and the base for converting to it can be any other base.

---

How can we calculate the number of digits in numbers in different bases?

If I know the number in base-10, how can I calculate the number of digits in the same number converted to base-16 (base-8, etc.) without performing a conversion?

Note: some Python or C code will be greatly appreciated.

Answer 1

Logarithms should not be slow. And you can easily calculate the logarithms to any base using this formula: logBaseN(x)=logBaseA(x)/logBaseA(N) - you can use ln (Base e = 2.718 ...) or logBase10 or whatever you have . Thus, you really do not need a program, formal should do this:

 num_digets(N, base) = 1 + floor(log(N) / log(base)) 

where N is your number and base base in which you want this number to be.

For a more detailed explanation, see here: http://www.mathpath.org/concepts/Num/numdigits.htm

Answer 2

Please note that your NumToStr() function in your Python code is incorrect due to a dropdown on your base, it should be:

 def NumToStr(num): str='' while num: str+=alpha[(num)%base] num=(num)/base return ''.join(list(reversed(str))) 

Note that checking that this function returns the correct result would find an error (for example, use alpha="0123456789" ).

With this fix, we get the correct number of digits using this formula:

 nDigits = int(ceil(log(nmb, base))) 

except for the exact power of the base ( base**0 , base**1 , base**2 , etc.), where it is exactly one less than it should be. This can be fixed by slightly changing the forum:

 nDigits = 1 + floor(log(nmb, base)) 

Note that even this may seem unsuccessful for some inputs (for example, converting from base-10 to base-10 incorrectly indicates 3 digits for 1000 and 6 digits for 1,000,000). This is apparently due to the inprecision float inherent, for example:

 print floor(log(1000, 10)) 

outputs 2 instead of the expected 3 .

As for your mention of performance, I wouldn't worry about performance issues for such trivial code until you have done the profiling / benchmarking, which shows that this is a problem. For example, your "very slow" C code will occupy no more than 38 divisions by 10 for a 128-bit number. If you need better performance than this, you will run into the same problem with any trivial method mentioned here. The fastest thing I can think of is the regular log() function using a combination of a lookup table and linear interpolation, but you have to be careful with the accuracy you get.

Answer 3

I'm not sure I understand your question. When you say that your seed is in base b1, does this mean that you represent it as a string in base b1? Perhaps you want to build some table that tells you which number in the base b1 matches b2, b2 ^ 2, b2 ^ 3, ... and then compare your number with these numbers to see where it fits.

Otherwise, I would go with the algorithm you specified, which can be easily applied to any database.

Input: your integer x, base b2, which you want to count digits.

 int number_of_digits (int x, int b2) { int n = 0; while (x >0) { x/=b2; n++; } return n; } 

Both methods are only linear in n.

EDIT . If you want to be faster, you can implement this as a binary search. Then you can get O (log (n)).