Sometimes, we need to know the number of digits in an integer. There are many methods, which could do this work well. Here we list some of them, and compare their performance in different circumstances. Firstly, we post the source code of the testing program.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | // Author: Sheng Yu // Time: 02/14/2013 // // A toy program to test some methods to get the number of digits // of an integer. // // Test environment: gcc (GCC) 4.1.2 20080704 (Red Hat 4.1.2-52) // Linux in X86_64 // #include <stdio.h> #include <time.h> #include <math.h> #include <string.h> int intlen_div(unsigned long long int num){ int len = 1; while(num/10!=0){ ++len; num /= 10; } return len; } int intlen_asstr(unsigned long long int num){ static char str_temp[25]; // Enough spaces to store the string for 2**64-1 sprintf(str_temp,"%llu",num); return strlen(str_temp); } int intlen_bruteforce(unsigned long long int num){ // Only conside the num less than 2**64-1 (18446744073709551615) if( num >= 10000000000000000000ULL ) return 20; else if( num >= 1000000000000000000 ) return 19; else if( num >= 100000000000000000 ) return 18; else if( num >= 10000000000000000 ) return 17; else if( num >= 1000000000000000 ) return 16; else if( num >= 100000000000000 ) return 15; else if( num >= 10000000000000 ) return 14; else if( num >= 1000000000000 ) return 13; else if( num >= 100000000000 ) return 12; else if( num >= 10000000000 ) return 11; else if( num >= 1000000000 ) return 10; else if( num >= 100000000 ) return 9; else if( num >= 10000000 ) return 8; else if( num >= 1000000 ) return 7; else if( num >= 100000 ) return 6; else if( num >= 10000 ) return 5; else if( num >= 1000 ) return 4; else if( num >= 100 ) return 3; else if( num >= 10 ) return 2; else if( num >= 0 ) return 1; } int main(){ // In our example, we only conside positive integers less than 2**64-1 unsigned long long int testnum = 0x1; clock_t t; int index = -1; int len = 0; // The first method, get the number of digits using a mathematical // computation. This method only contains one sentence, which seems // quite simply. t = clock(); index = -1; while(++index < 0xFFFFFF){ if(testnum == 0){ len = 0; } else{ len = (int)log10(testnum)+1; } } t = clock()-t; printf("The resulf of log10 based length is %dn",len); printf ("It took me %d clicks (%f seconds) to run 0xFFFFFF times.n", (int)t,((float)t)/CLOCKS_PER_SEC); // The second method prints the number as a string into a buffer, // and then computes the string length. The method is more // time-consuming than the first one. t = clock(); index = -1; while(++index < 0xFFFFFF){ len = intlen_asstr(testnum); } t = clock()-t; printf("nThe resulf of string based length is %dn",len); printf ("It took me %d clicks (%f seconds) to run 0xFFFFFF times.n", (int)t,((float)t)/CLOCKS_PER_SEC); // The third method iteratively uses a series of even division // to estimate the number of digits. This method has a long // code segment. t = clock(); index = -1; while(++index < 0xFFFFFF){ len = intlen_div(testnum); } t = clock()-t; printf("nThe result of division based length is %dn",len); printf ("It took me %d clicks (%f seconds) to run 0xFFFFFF times.n", (int)t,((float)t)/CLOCKS_PER_SEC); // The fourth method computes it in a brute force manner. // The codes seem long, redundant, and a little ugly. // But it is quite efficient. t = clock(); index = -1; while(++index < 0xFFFFFF){ len = intlen_bruteforce(testnum); } t = clock()-t; printf("nThe result of brute force based length is %dn",len); printf ("It took me %d clicks (%f seconds) to run 0xFFFFFF times.n", (int)t,((float)t)/CLOCKS_PER_SEC); return 0; } |
We tested the performance on Linux with Intel(R) Xeon(R) E5620 and 12G memory. The result is as following:
Method | Total Running Time (for 0xFFFFFF Rounds), in seconds | |||||
| Num=0 | 1 | 0xFFFF | 0xFFFFFFFF | 0xFFFFFFFFFFFF | 0xFFFFFFFFFFFFFFFF | |
| Log10 | N/A | 1.51 | 1.64 | 1.46 | 1.50 | 1.53 |
| Sprintf | 2.39 | 2.17 | 2.54 | 3.12 | 3.68 | 4.31 |
| Division | 0.06 | 0.06 | 0.95 | 2.07 | 3.18 | 4.30 |
| Brute | 0.35 | 0.35 | 0.31 | 0.23 | 0.16 | 0.07 |
The cost of log10 method is stable, no matter the number is big or small.
The sprintf method is always the slowest solution.
The division method is quick when the number is small.
The brute force method is ugly, but always efficient.
More discussion and an optimization solution for worst cases are in the next article here.