How many digits are in this database?

Question

The task is to obtain a formula for determining the number of digits that a given decimal number in a given database can have.

For example: The decimal number 100006 can be represented by 17.11.9.8.7.6.8 digits in bases 2,3,4,5,6,7,8 respectively.

Well, the formula we obtained looks like this: (log10 (num) / log10 (base)) + 1.

in C / C ++ I used this formula to calculate the above results.

long long int size = ((double)log10(num) / (double)log10(base)) + 1.0;

But, unfortunately, the formula does not give the correct answer in some cases, for example:

 Number 8 in base 2 : 1,0,0,0 Number of digits: 4 Formula returned: 3 Number 64 in base 2 : 1,0,0,0,0,0,0 Number of digits: 7 Formula returned: 6 Number 64 in base 4 : 1,0,0,0 Number of digits: 4 Formula returned: 3 Number 125 in base 5 : 1,0,0,0 Number of digits: 4 Formula returned: 3 Number 128 in base 2 : 1,0,0,0,0,0,0,0 Number of digits: 8 Formula returned: 7 Number 216 in base 6 : 1,0,0,0 Number of digits: 4 Formula returned: 3 Number 243 in base 3 : 1,0,0,0,0,0 Number of digits: 6 Formula returned: 5 Number 343 in base 7 : 1,0,0,0 Number of digits: 4 Formula returned: 3 

So, the error is 1 digit. I just want someone to help me correct the formula so that it works for all possible cases.

Edit: According to input specification, I have to deal with cases like 10000000000, i.e. 10 ^ 10, I don’t think log10 () in C / C ++ can handle such cases? Therefore, any other procedure / formula for this problem will be highly appreciated.

Answer 1

There are quick floating point operations in the compiler settings. You need accurate swimming operations. The fact is that log10 (8) / log10 (2) is always 3 in math. But maybe your result is 2.99999, for example. This is bad. You should add a small supplement, but not 0.5. It should be around .00001 or something like that.

Almost true formula:

 int size = static_cast<int>((log10((double)num) / log10((double)base)) + 1.00000001); 

Truly true solution

You should check the result of your formula. Compexity O(log log n) or O(log result) !

 int fast_power(int base, int s) { int res = 1; while (s) { if (s%2) { res*=base; s--; } else { s/=2; base*=base; } } return res; } int digits_size(int n, int base) { int s = int(log10(1.0*n)/log10(1.0*base)) + 1; return fast_power(base, s) > n ? s : s+1; } 

This test is better than the Brute-force test with base multiplication.

Answer 2

One of the following actions will be performed:

 >>> from math import * >>> def digits(n, b=10): ... return int(1 + floor(log(n, b))) if n else 1 ... >>> def digits(n, b=10): ... return int(ceil(log(n + 1, b))) if n else 1 ... 

The first version is explained at mathpath.org . In the second version + 1 it is necessary to give the correct answer for any number n, which is the smallest number with d-digits in the base b. That is, those numbers that are written in the database b ... 10 ... 0. Note that input 0 should be considered as a special case.

Decimal examples:

 >>> digits(1) 1 >>> digits(9) 1 >>> digits(10) 2 >>> digits(99) 2 >>> digits(100) 3 

Binary:

 >>> digits(1, 2) 1 >>> digits(2, 2) 2 >>> digits(3, 2) 2 >>> digits(4, 2) 3 >>> digits(1027, 2) 11 

Change The OP indicates that the log solution may not work for large inputs. I do not know about this, but if so, the following code should not be destroyed, because it uses only integer arithmetic (this time in C):

 unsigned int digits(unsigned long long n, unsigned long long b) { unsigned int d = 0; while (d++, n /= b); return d; } 

This code is likely to be less efficient. And yes, it was written for maximum points of confusion. He simply uses the observation that every number has at least one digit and that every division by b that does not give 0 implies the presence of an additional digit. A more readable version is as follows:

 unsigned int digits(unsigned long long n, unsigned long long b) { unsigned int d = 1; while (n /= b) { d++; } return d; } 

Answer 3

The number of digits digits in a given base

Answer 4

Since your formula is correct (I just tried it), I would think that this is a rounded error in your division, as a result of which the number will be slightly less than the integer value that it should be. So when you truncate an integer, you lose 1. Try adding another 0.5 to your final value (so truncating is actually a round operation).

Answer 5

What you want is the ceiling (= the smallest integer no more) log _b (n + 1), and not what you are currently calculating, floor (1 + log _{bsub> (n)).}

You can try:

 int digits = (int) ceil( log((double)(n+1)) / log((double)base) ); 

Answer 6

Using the formula,

 log(8)/log(2) + 1 = 4 

the problem is the accuracy of the calculation of the logarithm. Using

 ceil(log(n+1)/log(b)) 

should solve this problem. This is not quite the same as

 ceil(log(n)/log(b)) 

because it gives an answer of 3 for n = 8 b = 2 and does not match

 log(n+1)/log(b) + 1 

because it gives answer 4 for n = 7 b = 2 (when calculating to full accuracy).

I really get some interesting results from implementing and compiling the first form with g ++:

 double n = double(atoi(argv[1])); double b = double(atoi(argv[2])); int i = int(std::log(n)/std::log(b) + 1.0); 

fails (IE gives an answer of 3), and

 double v = std::log(n)/std::log(b) + 1.0; int i = int(v); 

successful (gives an answer of 4). Looking at him, I think the third form

 ceil(log(n+0.5)/log(b)) 

will be more stable because it avoids the “critical” case where n (or n + 1 for the second form) is an integer power of b (for integer values ​​of n).

Answer 7

As others have noted, you have a rounding error, but the proposed solutions simply move the danger zone or reduce it, they do not eliminate it. If your numbers are integers, you can check - using integer arithmetic - that one base power is less than or equal to your number, and the next is above it (the first power is the number of digits). But if you use floating point arithmetic anywhere in the chain, then you will be vulnerable to error (if your base is not equal to two, or maybe even then).

EDIT:
Here's a crude but effective solution in integer arithmetic. If your integer classes may contain numbers greater than the base number *, this will give the correct answer.

   size = 0, k = 1;
   while (k & lt = num)
     {
       k * = base;
       size + = 1;
     }

Answer 8

It may be useful to wrap a rounding function (e.g. + 0.5) in your code somewhere: it is likely that the division produces (e.g.) 2.99989787, to which 1.0 is added, giving 3.99989787, and when it converts to int, it gives 3 .

Answer 9

It seems like the formula suits me:

 Number 8 in base 2 : 1,0,0,0 Number of digits: 4 Formula returned: 3 log10(8) = 0.903089 log10(2) = 0.301029 Division => 3 +1 => 4 

So this is definitely just a rounding error.

Answer 10

Floating point rounding issues.

 log10(216) / log10(6) = 2.9999999999999996 

But you cannot add 0.5, as suggested, because this will not work for the following

 log10(1295) = log10(6) = 3.9995691928566091 // 5, 5, 5, 5 log10(1296) = log10(6) = 4.0 // 1, 0, 0, 0, 0 

Perhaps using the log (value, base) function avoids these rounding errors.

Answer 11

I think the only way to get a rounding exception without eliminating other errors is to use or implement integer logarithms.

Answer 12

Here is the solution in bash:

 % digits() { echo $1 $2 opq | dc | sed 's/ .//g;s/.//' | wc -c; } % digits 10000000000 42 7 

Answer 13

 static int numInBase(int num, int theBase) { if(num == 0) return 0; if (num == theBase) return 1; return 1 + numInBase(num/theBase,theBase); }