Fastest way to calculate the decimal length of an integer? (.NETWORK)

Question

I have a code that does a lot of comparisons of 64-bit integers, however it should consider the length of the number as if it were formatted as a string. I can’t change the call code, only the function.

The easiest way (besides .ToString (). Length):

(int)Math.Truncate(Math.Log10(x)) + 1; 

However, this works rather poorly. Since my application sends only positive values, and the lengths are pretty evenly distributed between 2 and 9 (with some offset to 9), I precomputed the values ​​and have if statements:

 static int getLen(long x) { if (x < 1000000) { if (x < 100) return 2; if (x < 1000) return 3; if (x < 10000) return 4; if (x < 100000) return 5; return 6; } else { if (x < 10000000) return 7; if (x < 100000000) return 8; if (x < 1000000000) return 9; return (int)Math.Truncate(Math.Log10(x)) + 1; // Very uncommon } } 

This allows you to calculate the length on average 4 times.

So, are there any other tricks I can use to speed up this feature?

Edit: this will work as 32-bit code (Silverlight).

Update:

I accepted Norman’s suggestion and changed the ifs a bit, resulting in an average of only 3 comparisons. According to Sean's comment, I deleted Math.Truncate. Together, this increased by about 10%. Thank!

Answer 1

Two suggestions:

• Profile and first establish common cases.
• Do a binary search to minimize the number of comparisons in the worst case. You can choose one of 8 options using only three comparisons.

This combination probably does not buy you much if the distribution is not very distorted.

Answer 2

From Sean Anderson Beat Tweedling Hacks :

Find the integer log base of 10 integer

 unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of int r; // result goes here int t; // temporary static unsigned int const PowersOf10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; t = (IntegerLogBase2(v) + 1) * 1233 >> 12; // (use a lg2 method from above) r = t - (v < PowersOf10[t]); 

The integer base base 10 is calculated by the formula, first using one of the methods above to find the base of logs 2. According to the ratio log10 (v) = log2 (v) / log2 (10), we need to multiply it by 1 / log2 (10), which is approximately 1233/4096 or 1233 followed by the right offset 12. You must add one because the IntegerLogBase2 rounds down. Finally, since the value of t is only an approximation that can be turned off by one, the exact value is determined by subtracting the result v <PowersOf10 [t].

This method performs 6 more operations than IntegerLogBase2. This can be accelerated (on machines with fast memory access) by changing the base of log 2 the search method of the table above so that the records contain what is calculated for t (i.e., pre-add, -set and -shift). This will require only 9 operations to find log base 10, assuming that 4 tables were used (one for each byte v).

Regarding the calculation of IntegerLogBase2, several alternatives are presented on this page. This is a great reference for all kinds of highly optimized whole operations.

A variant of your version also exists, except that it is assumed that the values ​​(and not the base of the base of 10 values) are uniformly distributed and, therefore, an exponentially ordered search:

Find the integer logarithmic base of 10 integer in an obvious way

 unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of int r; // result goes here r = (v >= 1000000000) ? 9 : (v >= 100000000) ? 8 : (v >= 10000000) ? 7 : (v >= 1000000) ? 6 : (v >= 100000) ? 5 : (v >= 10000) ? 4 : (v >= 1000) ? 3 : (v >= 100) ? 2 : (v >= 10) ? 1 : 0; 

This method works well when the input is evenly distributed over 32-bit because 76% of the inputs at first glance, 21% at the second are compared 2% caught by the third, and so on (chopping the remaining down 90% with each comparison). As a result, less than 2.6 operations per average are required.

Answer 3

Here's the binary search version that I tested, which works with 64-bit integers using exactly five comparisons each time.

 int base10len(uint64_t n) { int len = 0; /* n < 10^32 */ if (n >= 10000000000000000ULL) { n /= 10000000000000000ULL; len += 16; } /* n < 10^16 */ if (n >= 100000000) { n /= 100000000; len += 8; } /* n < 100000000 = 10^8 */ if (n >= 10000) { n /= 10000; len += 4; } /* n < 10000 */ if (n >= 100) { n /= 100; len += 2; } /* n < 100 */ if (n >= 10) { return len + 2; } else { return len + 1; } } 

I doubt it will be faster than what you are already doing. But it is predictable.

Answer 4

I did some testing, and this seems to be 2-4 times faster than the code you have now:

 static int getLen(long x) { int len = 1; while (x > 9999) { x /= 10000; len += 4; } while (x > 99) { x /= 100; len += 2; } if (x > 9) len++; return len; } 

Edit:
Here is a version that uses more Int32 operations that should work better if you don't have an x64 application:

 static int getLen(long x) { int len = 1; while (x > 99999999) { x /= 100000000; len += 8; } int y = (int)x; while (y > 999) { y /= 1000; len += 3; } while (y > 9) { y /= 10; len ++; } return len; } 

Answer 5

You commented on the code that 10 digits or more is very unusual, so your original solution is not bad

Answer 6

I have not tested this, but a change to the basic law reads:

Log10 (x) = Log2 (x) / Log2 (10)

Log2 should be slightly faster than Log10 if it was implemented correctly.

Answer 7

 static int getDigitCount( int x ) { int digits = ( x < 0 ) ? 2 : 1; // '0' has one digit,negative needs space for sign while( x > 9 ) // after '9' need more { x /= 10; // divide and conquer digits++; } return digits; } 

Answer 8

not sure if this is faster or not .. but you can always count ...

 static int getLen(long x) { int len = 1; while (x > 0) { x = x/10; len++ }; return len } 

Answer 9

What do you mean by length? The number of zeros or everything else? It makes important numbers, but you get the general idea.

 public static string SpecialFormat(int v, int sf) { int k = (int)Math.Pow(10, (int)(Math.Log10(v) + 1 - sf)); int v2 = ((v + k/2) / k) * k; return v2.ToString("0,0"); } 

Answer 10

This is an easy way.

 private static int GetDigitCount(int number) { int digit = 0; number = Math.Abs(number); while ((int)Math.Pow(10, digit++) <= number); return digit - 1; } 

If number is unsigned int, then "Math.Abs ​​(number)" is optional.

I made an extension method with all numeric types.

  private static int GetDigitCount(dynamic number) { dynamic digit = 0; number = Math.Abs(number); while ((dynamic)Math.Pow(10, digit++) <= number) ; return digit - 1; } public static int GetDigit(this int number) { return GetDigitCount(number); } public static int GetDigit(this long number) { return GetDigitCount(number); } 

then you use this.

 int x = 100; int digit = x.GetDigit(); // 3 expected.