How many digits in this base?

Question

The problem is to derive a formula for determining number of digits a given decimal number could have in a given base.

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 I derived so far is like this : (log10(num) /log10(base)) + 1.

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

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

But sadly the formula is not giving correct answer is some cases,like these :

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 by 1 digit.I just want somebody to help me to correct the formula so that it work for every possible cases.

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

Answer 1

Either of the following will work:

>>> 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 the + 1 is necessary to yield the correct answer for any number n that is the smallest number with d digits in base b. That is, those numbers which are written 10...0 in base b. Observe that input 0 must be treated 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

Edit: The OP states that the log solution may not work for large inputs. I don't know about that, but if so, the following code should not break down, because it uses integer arithmetic only (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 will probably be less efficient. And yes, it was written for maximum obscurity points. It simply uses the observation that every number has at least one digit, and that every divison by b which does not yield 0 implies the existence of an additional digit. A more readable version is the following:

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

Answer 2

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

Answer 3

Using your formula,

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

the problem is in the precision of the logarithm calculation. Using

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

ought to resolve that problem. This isn't quite the same as

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

because this gives the answer 3 for n=8 b=2, nor is it the same as

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

because this gives the answer 4 for n=7 b=2 (when calculated to full precision).

I actually get some curious resulting 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 the answer 3), while,

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

succeeds (gives the answer 4). Looking at it some more I think a third form

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

would be more stable, because it avoids the "critical" case when n (or n+1 for the second form) is an integer power of b (for integer values of n).

Answer 4

There are fast floating operations in your compiler settings. You need precise floation operations. The thing is that log10(8)/log10(2) is always 3 in math. But may be your result is 2.99999, for expample. It is bad. You must add small additive, but not 0.5. It should be about .00001 or something like that.

Almost true formula:

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

Really true solution

You should check the result of your formula. Compexity is 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 check is better than Brute-force test with base multiplications.

Answer 5

Here is a solution in bash:

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


% digits 10000000000 42
7

Answer 6

As others have pointed out, you have rounding error, but the proposed solutions simply move the danger zone or make it smaller, they don't eliminate it. If your numbers are integers then you can verify -- using integer arithmetic -- that one power of the base 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 (unless your base is a power of two, and maybe even then).

EDIT:
Here is crude but effective solution in integer arithmetic. If your integer classes can hold numbers as big as base*number, this will give the correct answer.

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

Answer 7

I think that the only way to get the rounding error eliminated without producing other errors is to use or implement integer logarithms.

Answer 8

What you want is ceiling ( = smallest integer not greater than) log_b (n+1), rather than what you're calculating right now, floor(1+log_b(n)).

You might try:

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

Answer 9

Floating point rounding issues.

log10(216) / log10(6) =  2.9999999999999996

But you cannot add 0.5 as suggested, because it would 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

Maybe using the log(value, base) function would avoid these rounding errors.

Answer 10

Looks like the formula is right to 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 it's definitely just a rounding error.

Answer 11

It may be beneficial to wrap a rounding function (e.g. + 0.5) into your code somewhere: it's quite likely that the division is producing (e.g.) 2.99989787, to which 1.0 is added, giving 3.99989787 and when that's converted to an int, it gives 3.

Answer 12

Since your formula is correct (I just tried it), I would think that it's a rounding error in your division, causing the number to be just slightly less than the integer value it should be. So when you truncate to an integer, you lose 1. Try adding an additional 0.5 to your final value (so that truncating is actually a round operation).

Answer 13

Number of digits of a numeral in a given base