Count number of digits - which method is most efficient?

Question

There are more than one solution for finding the-number-of-digits in a given number.

For example:

Method-1:

int findn(int num)
{
    char snum[100];
    sprintf(snum, "%d", num);
    return strlen(snum);
}

Method-2:

int findn(int num)
{
    if (num == 0) return 1;
    int n = 0;
    while(num) {
        num /= 10;
        n++;
    }
    return n;
}

Method-3:

int findn(int num)
{
    /* math.h included */
    return (int) log10(num) + 1;
}

The question is - what is the most efficient method? I know method-2 is O(n) but what about method-1 and method-3? How do I find the run-time complexity of library functions?

Answer 1

The following is even more efficient:

int findn(int num)
{
   if ( num < 10 )
      return 1;
   if ( num < 100 )
      return 2;
   //continue until max int
}

You could optimize this even further by doing a binary search, but that would be overkill.

Answer 2

The GCC/Clang __builtin_clz() or Microsoft Visual C _BitScanReverse() intrinsic functions compile to a single machine instruction on many machines. You can use this as the basis for an O(1) solution. Here's a 32-bit implementation:

#include <limits.h>
#include <stdint.h>

/* Return the number of digits in the decimal representation of n. */
unsigned digits(uint32_t n) {
    static uint32_t powers[10] = {
        0, 10, 100, 1000, 10000, 100000, 1000000,
        10000000, 100000000, 1000000000,
    };
    static unsigned maxdigits[33] = {
        1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5,
        5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 
    };
    unsigned bits = sizeof(n) * CHAR_BIT - __builtin_clz(n);
    unsigned digits = maxdigits[bits];
    if (n < powers[digits - 1]) {
        -- digits;
    }
    return digits;
}

Answer 3

As it currently stands, the accepted and most highly approved answer is (still) incorrect for negative numbers. If the answerer were to take the time to test it and find out that it's broken for negative numbers, he likely would have wasted more time than the machine ever would by simply using snprintf, i.e.

int count_digits(int arg) {
    return snprintf(NULL, 0, "%d", arg) - (arg < 0);
}

We're not in the 1980s anymore; stop coding as though we are. I'm a C-standard zealot and my favourite answer given here was Tao Feng's answer... but even that didn't go into why it's the most efficient answer so far; in this answer I intend to show that his answer can be improved further by considering the following:

• Programmer productivity is more important than code efficiency, because it will almost certainly cost more time to write and test new functions properly than it will for a few microseconds of runtime.
• Reusing the same standard library functions that other programs commonly use (probably) keeps those standard libraries in the CPU cache. A cache miss (for example, when your code needs to be copied from RAM into the CPU) can cost up to 50 CPU instructions, not to mention the other code may end up causing another cache miss to put snprintf back into the cache anyway.
• Eliminating storage requirements might expose extra optimisations.

---

The following describes the micro-optimisation which hinders your productivity. Due to the lack of information you've provided in your answer, nobody who answers the question as it currently stands can provide any proof without making assumptions about:

• When we optimise we need to find the most significant bottleneck in the full solution (the problem that your program's designed to solve). There are two possibilities here: A) You want to calculate the number of bytes to allocate in order to store a string containing these digits; B) You just want to count the number of digits or whatever for kicks. More on these later. For now it's important to realise you're probably talking about part of a solution, and that part might not be the most significant bottleneck.
• The compiler you're using, the OS you're using and the machine you're using (including RAM speed, since some of us are introducing potential cache misses that are affected more by slow memory than by fast memory) might affect the most significant bottleneck. Some compilers are different to others, and will optimise some pieces of code better for some OSes, CPUs, etc than others.

You can avoid micro-optimisation by measuring bottlenecks, i.e. by profiling ("benchmarking") each of these solutions on your system, assuming they even solve your problems properly. If a solution doesn't solve the problem, it's not a solution, so it shouldn't be considered... When done correctly this should eliminate the micro-optimisation. Some compilers even provide intelligent profile-guided optimisation which commonly shaves 20-30% by reorganising branches and objects for cache locality, and do so automatically.

I've already covered counting digits, which I think most certainly answers your question, but there are cases where you might think you need to count digits when you don't, and the ability to remove the overhead of counting digits might present a very desirable optimisation, both in man hours and in machine hours.

For example, if you want to calculate the number of bytes to allocate in order to store a string containing these digits, you shouldn't use any runtime because a preprocessor macro can be used to calculate the maximum number of digits (or characters, including the sign), and any precious bytes of temporary storage you try to save will be well outnumbered by machine code bytes added in logic, which seems like a steep cost to me. There's also a benefit for the programmer to use a preprocessor macro; the same macro could be used for any integer type. See my answer to this question for a solution to this problem; after all, there's no point repeating myself...

Answer 4

I think maybe you can write the first method as

int findn(int num)
{
    char snum[100];    
    return  sprintf(snum, "%d", num);
}

because sprintf will return the number of chars written and you can save the call to strlen.

As for the efficiency, I think it depends on the implementation of sprintf, you may need to find the source of sprintf and see if it is efficiency of doing this.

Answer 5

One liner: for(digits = 0; num > 0; digits++) num /= 10;

Answer 6

I think sprintf() will use your method 2 to print the number (to determine the length of the string to print, and then to print each character of the string), so it will be inherently slower.

Number 3 would probably involve some polynomial approximation of ln() wich will involve more that 1 division, so I guess it will be slower as well (here's a fast ln() implementation, still involving float division... so WAY slower).

So my tentative guess is, method 2 is the way to go.

Please note that this is a quite liberal way to approach this problem. I guess testing a good old timed million-iteration with each function will tell you the result. But it would bee too bruteforce, wouldn't it?

Note that only method 2 will give you the real results, the others have flaws that have to be adjusted to be correct (see Aaron's answer). So simply pick method 2.

Answer 7

Try binary search. For the sake of clarity, let's assume signed 32-bit integers. First, check if x < 10000. Next, depending on the answer, if x < 100 or x < 1000000, and so on.

That's O(log n), where n is the number of digits.

Answer 8

These functions give drastically different results for non-positive numbers (the worst is method 3), so comparing their time complexities is of dubious value. I would use the one that gives the answer required in all cases; without context, we can't know what that is (it's probably not method 3).

For method 1, findn(0) == 1, and findn(-n) == digits in n + 1 (because of the negative sign).

For method 2, findn(0) == 0, and findn(-n) == digits in n.

For method 3, findn(0) == INT_MIN, and findn(-n) == INT_MIN as well.

Answer 9

This is my solution... it'll count up to 100 digits or you know whatever you want it to count up to.

max_digits = 100

int numdigits(int x) {
  for (int i = 1; i < max_digits; i++) {
    if (x < pow(10, i)) {
      return i;
    }
  }
  return 0;
}

Answer 10

printf function will return the number of digits successfully printed.

int digits,n=898392;

digits=printf("%d",n);
printf("Number of digits:%d",digits);

Output:

898392

Number of digits:6

Answer 11

Using log may be a good option...

1. If the target machine has hardware support for it
2. If you are sure that int can be cast into double and back without any loss of precision.

Sample implementation...

int num_digits(int arg) {
    if (arg == 0) {
        return 1;
    }

    arg = abs(arg);

    return (int)log10(arg)+1;
}

Answer 12

log10(x) + 1 will count the digits for x > 0, but another approach may be desired:

1. log2(x) = size_of(x) - 1 - clz(x) will calculate log2 as an integer.
2. log_b(x) = log2(x) / log2(b) will do a base conversion.
3. The log2(10) divisor becomes 3 for base 10.
4. The log2(x) dividend becomes 31 - clz(x) for 32-bit integers.

You can even count hex digits or any other base with this.

uint32_t count_dec_digits(uint32_t n) {
    return 1 + (31 - __builtin_clz(n)) / 3;
}

uint32_t count_hex_digits(uint32_t n) {
    return 1 + (31 - __builtin_clz(n)) / 4;
}

int main() {
    printf("%d", count_dec_digits(1234567)); // 7
    printf("%d", count_hex_digits(0x12345)); // 5
}

Answer 13

Variant of the function suggested by @AShelly for signed and unsigned 64 bits numbers with the check for 0 (https://godbolt.org/z/cqeKEj4rj, contains also some testing code).

uint8_t digits_u64(uint64_t number) {
    static uint8_t maxdigits[] = {
        1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6,
        7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11,
        12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 15, 15, 15,
        16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 19, 19, 19, 19, 20, 
    };

    static uint64_t powers[] = {
        0U, 1U, 10U, 100U, 1000U, 10000U, 100000U, 1000000U, 10000000U,
        100000000U, 1000000000U, 10000000000U, 100000000000U,
        1000000000000U, 10000000000000U, 100000000000000U,
        1000000000000000U, 10000000000000000U, 100000000000000000U,
        1000000000000000000U, 10000000000000000000U, 
    };

    if (number == 0) {
        return 1;
    }

    unsigned bits = sizeof(number) * CHAR_BIT - __builtin_clzll(number);
    unsigned digits = maxdigits[bits];

    if (number < powers[digits]) {
        --digits;
    }
    
    return digits;
}

uint8_t digits_i64(int64_t number) {
    int add_minus_sign = number < 0U ? 1 : 0;
    if (add_minus_sign) {
        number *= -1;
    }

    return digits_u64(number) + add_minus_sign;
}