C: Safe to Calculate Number of Digits in Integer (N) of Base (b) Using Logarithmic Functions

Question

Given the formula:

NUM_DIGITS_IN_N_FOR_BASE_B = 1 + floor(ln(abs(N)) / ln(b))

such that b is a base between 2 and 36 and N is of type int.

According to this post post 1 it seems okay to assume that the value returned for the range of all integers [INT_MIN, INT_MAX] would work with no round-off or overflow error. I am a bit skeptical about this. My skepticism comes from a recent post of mine @post 2. If using the mathematical definition is not "safe" in a computer program, is there another trick to use to compute the number of digits in a number N given a base b?

It is not safe, as of the standard. I'd also suspect rounding errors. Better use an integer algorithm; note you likely don't need the exact logarithm, but an integer result. The basic idea is to find the MSbit. — too honest for this site, Feb 23 '16 at 19:22
@user3386109 One could add special cases for INT_MIN or 0 in a very trivial manner. — Matthew Hoggan, Feb 23 '16 at 20:17
@user3386109 nice, which is what I thought would happen. Now the question remains.What is the best way to calculate the number of digits in a base b number. — Matthew Hoggan, Feb 23 '16 at 20:30

score 2 · Accepted Answer · answered Feb 23 '16 at 20:49

Is it safe to calculate the number of digits in an integer N in base b using logarithmic functions?

No absolutely not, due to rounding errors. Specifically, the risk is that log(N)/log(b) will be slightly less than the exact value. This is most likely to occur when N is an exact multiple of b.

How does one count the number of digits in an integer N in base b?

Divide N by b in a loop until N is zero. See the countDigits function in the code below. Handling values of N <= 0 is left as an exercise for the reader.

For example, consider the following code

int countDigits( int N, int b )
{
    int count;
    for ( count = 0; N; count++ )
        N /= b;
    return count;
}

int main( void )
{
    int N, b;
    if ( scanf( "%d %d", &N, &b ) != 2 )
        return 1;

    printf( "log(%3d) = %.50lf\n", N, log(N) );
    printf( "log(%3d) = %.50lf\n", b, log(b) );
    printf( "ratio    = %.50lf\n", log(N)/log(b) );
    printf( "expected = %d\n", countDigits(N, b) );
    double digits = 1 + floor(log(N) / log(b));
    printf( "computed = %lf\n", digits );
}

If the user enters 243 for N, and 3 for b, the output is

log(243) = 5.49306144334054824440727315959520637989044189453125
log(  3) = 1.09861228866810978210821758693782612681388854980469
ratio    = 4.99999999999999911182158029987476766109466552734375
expected = 6
computed = 5.000000

The expected number of digits is 6 since 243₁₀ = 100000₃. The problem with the logarithm method is that either log(243) is slightly too small or log(3) is slightly too large, resulting in a ratio that is just below 5 when it should be exactly 5.

score 2 · Answer 2 · edited May 23 '17 at 12:02

2

@user3386109 well answered the first part of the post.

For the 2nd part:

is there another trick to use to compute the number of digits in a number N given a base b.?

// Works for all `N` including `0`, `INT_MIN`
int num_digs = 1;
int T = N;
while (T /= b) num_digs++;

This calculates the number of digits. Does not count a sign character.

edited May 23 '17 at 12:02

Community

1
1

answered Feb 23 '16 at 22:02

chux - Reinstate Monica

143,097
13
135
256

I wish I could select to posts as answers. – Matthew Hoggan Feb 23 '16 at 22:30

C: Safe to Calculate Number of Digits in Integer (N) of Base (b) Using Logarithmic Functions

2 Answers2