In this article, an stable-cost method is proposed and tested. Previously, the test result showed, the performance of brute force method is the best. Let the number of digits be n. In the best case, in which the integer is equal to or greater than 1019, we need one comparison and return the result. While in the worst case, in which the integer is less than 10, we need twenty comparisons.
We could easily get the asymptotic algorithm complexity of the original brute force method as O(n). But the algorithm complexity is meaningless here, because the maximum of n, being 20, is still so small.
Essentially, in the brute force method, we are finding an element (the integer) in a sorted list [0,unsigned long long int]. As a result, when searching, we could use binary search rather than sequential search in the brute force method to utilize the sorted attribution. The source code of optimized function is listed as follows.
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 | int intlen_bincomp(unsigned long long int num){ // Only conside the num less than 2**64-1 (18446744073709551615) // Compare the number in a better manner than brute force. // Using a binary tree could be more beautiful. // But anyway expanding comparison would be more efficient. if( num >= 10000000000 ){ // From 11 digits to 20 if( num >= 1000000000000000){ // From 16 to 20 digits if( num >= 100000000000000000 ){ // From 18 to 20 digits if( num >= 10000000000000000000ULL){ return 20; } else{ if(num >= 1000000000000000000){ return 19; } else{ return 18; } } } else{ // From 16 to 17 digits if(num >= 10000000000000000){ return 17; } else{ return 16; } } } else{ // From 11 to 15 digits if( num >= 1000000000000 ){ // From 13 to 15 digits if( num >= 100000000000000){ return 15; } else{ if(num >= 10000000000000){ return 14; } else{ return 13; } } } else{ // From 11 to 12 digits if(num >= 100000000000){ return 12; } else{ return 11; } } } } else{ // From 1 digits to 10 if( num >= 100000){ // From 6 to 10 digits if( num >= 10000000 ){ // From 8 to 10 digits if( num >= 1000000000){ return 10; } else{ if(num >= 100000000){ return 9; } else{ return 8; } } } else{ // From 6 to 7 digits if(num >= 1000000){ return 7; } else{ return 6; } } } else{ // From 1 to 5 digits if( num >= 100 ){ // From 3 to 5 digits if( num >= 10000){ return 5; } else{ if(num >= 1000){ return 4; } else{ return 3; } } } else{ // From 1 to 2 digits if(num >= 10){ return 2; } else{ return 1; } } } } } |
Theoretically, the best case need 4 comparisons, and the worst case need 5. The actual performance is listed in the following table.
Method | Total Running Time (for 0xFFFFFF Rounds), in seconds | |||||
| Num=0 | 1 | 0xFFFF | 0xFFFFFFFF | 0xFFFFFFFFFFFF | 0xFFFFFFFFFFFFFFFF | |
| Log10 | N/A | 1.15 | 1.27 | 1.27 | 1.27 | 1.18 |
| Sprintf | 2.19 | 2.18 | 2.58 | 3.15 | 3.70 | 4.36 |
| Division | 0.06 | 0.06 | 0.96 | 2.08 | 3.23 | 4.32 |
| Brute | 0.34 | 0.34 | 0.30 | 0.23 | 0.16 | 0.06 |
| Binary | 0.11 | 0.11 | 0.10 | 0.09 | 0.10 | 0.10 |
The performance of binary-search based method is pretty good, and spends approximately the same time no matter what is the input. In other words, the binary-search based method is the winner in worst cases.
But averagely, the brute force method is still the best. With original brute force method, 8446744073709551616 numbers are larger than or equal to 1019, and need only one comparison. Another 9*1018 numbers has 19 digits and need two comparisons. And so on. These numbers, which have 19 or more digits, take an overwhelming proportion of all. On average, we need 1.60 comparisons.
While in the binary search method, these numbers with 20 digits and 19 digits need 4 comparisons. Another 9*1017 numbers with 18 digits need 5 comparisons. And so on. On average, we need 4.05 comparisons with binary search method, which is much higher than the brute force algorithm (1.60).
Finally, is there any other way to improve the performance anymore? The answer is yes, and no. Theoretically, using a dictionary would not need any comparison, could return the result directly, and thus is the most time-saving solution. But in practice, using a dictionary need so much memory that it become unacceptable.