Some Methods to Get the Number of Digits in An Integer, and Their Performance (2)

6 Mar

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.

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=010xFFFF0xFFFFFFFF0xFFFFFFFFFFFF0xFFFFFFFFFFFFFFFF
Log10N/A1.151.271.271.271.18
Sprintf2.192.182.583.153.704.36
Division0.060.060.962.083.234.32
Brute0.340.340.300.230.160.06
Binary0.110.110.100.090.100.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.

Leave a Reply

Your email address will not be published. Required fields are marked *