Log10 function performance returning int

Question

Today I needed a cheap log10 function, from which I used only the int part. Assuming the result is flooring, so log10 999 would be 2. Would it be useful to write the function yourself? And if so, how would it be better to go. Assuming the code will not be optimized.

The log10 alternatives that I have are

• use a for loop dividing or multiplying by 10;
• Use a string parser (possibly very expensive)
• using the integer log2 () function multiplied by a constant.

Thanks in advance:)

Answer 1

The operation can be performed in (fast) constant time on any architecture that has a zero-start or similar instruction (which is the majority of architectures). Here's the C fragment I'm sitting in, calculates the number of digits in the base ten, which is essentially the same task (assumes a gcc-like compiler and a 32-bit int):

unsigned int baseTwoDigits(unsigned int x) { return x ? 32 - __builtin_clz(x) : 0; } unsigned int tenToThe[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, }; unsigned int baseTenDigits(unsigned int x) { unsigned int guess[33] = { 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9 }; unsigned int digits = guess[baseTwoDigits(x)]; return digits + (x >= tenToThe[digits]); } 

GCC and clang compile this to ~ 10 instructions on x86. With caution, you can speed up the assembly process.

The key concept is to use the (extremely cheap) base-two logarithm to quickly evaluate the base-ten logarithm; at this point, we need to compare only one force in ten to decide whether we need to correct guesses. This is much more effective than finding several degrees in ten to find the right one.

If the inputs are overwhelmingly biased to single and double digit numbers, linear scanning sometimes happens faster; for all other input distributions, this implementation tends to win quite conveniently.

Answer 2

If you want to have a faster log function, you need to get closer to their result. For instance. the exp function can be approximated using the “short” Taylor approximation. You can find approximate approximations for exp, log, root and power here

change You can find a short performance comparison here

Answer 3

Well, there the old standby mode is the function of the poor man magazine. (If you want to process more than 63 integers, change the first "if" to "while".)

 n = 1; if (v >= 1e32){n += 32; v /= 1e32;} if (v >= 1e16){n += 16; v /= 1e16;} if (v >= 1e8){n += 8; v /= 1e8;} if (v >= 1e4){n += 4; v /= 1e4;} if (v >= 1e2){n += 2; v /= 1e2;} if (v >= 1e1){n += 1; v /= 1e1;} 

so if you file 123456.7, here is how it goes:

 n = 1; if (v >= 1e32) no if (v >= 1e16) no if (v >= 1e8) no if (v >= 1e4) yes, so n = 5, v = 12.34567 if (v >= 1e2) no if (v >= 1e1) yes, so n = 6, v = 1.234567 so result is n = 6 

---

Here's an option that uses multiplication rather than division:

 int n = 1; double d = 1, temp; temp = d * 1e32; if (v >= temp){n += 32; d = temp;} temp = d * 1e16; if (v >= temp){n += 16; d = temp;} temp = d * 1e8; if (v >= temp){n += 8; d = temp;} temp = d * 1e4; if (v >= temp){n += 4; d = temp;} temp = d * 1e2; if (v >= temp){n += 2; d = temp;} temp = d * 1e1; if (v >= temp){n += 1; d = temp;} 

and the execution looks like this:

 v = 123456.7 n = 1 d = 1 temp = 1e32, if (v >= 1e32) no temp = 1e16, if (v >= 1e16) no temp = 1e8, if (v >= 1e8) no temp = 1e4, if (v >= 1e4) yes, so n = 5, d = 1e4; temp = 1e6, if (v >= 1e6) no temp = 1e5, if (v >= 1e5) yes, so n = 6, d = 1e5; 

Answer 4

One way to do this would be to subtract 10 degrees. These powers can be calculated and stored in a table. Here is an example in python:

 table = [10**i for i in range(1, 10)] # [10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000] def fast_log10(n): for i, k in enumerate(table): if n - k < 0: return i 

Usage example:

 >>> fast_log10(1) 0 >>> fast_log10(10) 1 >>> fast_log10(100) 2 >>> fast_log10(999) 2 fast_log10(1000) 3 

You can also use binary search with this table. Then the complexity of the algorithm would be only O (log (n)), where n is the number of digits. Here's a binary search example in C:

 long int table[] = {10, 100, 1000, 10000, 1000000}; #define TABLE_LENGHT sizeof(table) / sizeof(long int) int bisect_log10(long int n, int s, int e) { int a = (e - s) / 2 + s; if(s >= e) return s; if((table[a] - n) <= 0) return bisect_log10(n, a + 1, e); else return bisect_log10(n, s, a); } int fast_log10(long int n){ return bisect_log10(n, 0, TABLE_LENGHT); } 

Note for small numbers this method will be slower than the top one. Full code here .

Answer 5

Without any specifications, I will simply give a general answer:

The log function will be quite effective in most languages, since this is such a basic function.

The fact that you are only interested in integers may give you some advantage, but probably this is not enough to easily surpass built-in standard solutions.

One of the few things that I can think of faster than the built-in function is to search the table, so if you are only interested in numbers up to 10000, you can simply create a table that you can use to find any of these values ​​when you will need them.

Obviously, this solution will not scale well, but it may be exactly what you need.

---

Sidenote: if you are importing data, for example, it may be faster to view the length of a diecty string (instead of first converting the string to a number and looking at the value of the string). Of course, this will require that the input data be saved in the correct format, otherwise it will not bring you anything.