for instance,
n = 3432, result 4
n = 45, result 2
n = 33215, result 5
n = -357, result 3
I guess I could just turn it into a string then get the length of the string but that seems convoluted and hack-y.
Join Stack Overflow to learn, share knowledge, and build your career.
|
|
|||||||||||||||||||||
|
|
The recursive approach :-)
Or iterative:
Or raw speed:
Those above have been modified to better process MININT. On any weird systems that don't follow sensible 2n two's complement rules for integers, they may need further adjustment. The raw speed version actually outperforms the floating point version, modified below:
With a hundred million iterations, I get the following results:
That actually surprised me a little - I thought the Intel chips had a decent FPU but I guess general FP operations still can't compete with hand-optimized integer code. Update following stormsoul's suggestions: Testing the multiply-iterative solution by stormsoul gives a result of 4 seconds so, while it's much faster than the divide-iterative solution, it still doesn't match the optimized if-statement solution. Choosing the arguments from a pool of 1000 randomly generated numbers pushed the raw speed time out to 2 seconds so, while it appears there may have been some advantage to having the same argument each time, it's still the fastest approach listed. Compiling with -O2 improved the speeds but not the relative positions (I increased the iteration count by a factor of ten to check this). Any further analysis is going to have to get seriously into the inner workings of CPU efficiency (different types of optimization, use of caches, branch prediction, which CPU you actually have, the ambient temperature in the room and so on) which is going to get in the way of my paid work :-). It's been an interesting diversion but, at some point, the return on investment for optimization becomes too small to matter. I think we've got enough solutions to have answered the question (which was, after all, not about speed). Further update: This will be my final update to this answer barring glaring errors that aren't dependent on architecture. Inspired by stormsoul's valiant efforts to measure, I'm posting my test program (modified as per stormsoul's own test program) along with some sample figures for all methods shown in the answers here. Keep in mind this is on a particular machine, your mileage may vary depending on where you run it (which is why I'm posting the test code). Do with it as you wish:
And, in terms of results, here's the leader-board for my environment: Optimization level 0:
Optimization level 3:
|
|||||||||||||||||||||
|
|
Binary search pseudo algorithm to get no of digits of r in v..
|
|||||||||||||||||
|
|
The shortest answer: |
|||||||||||||||||||||
|
|
Divide by 10 in a loop until the result reaches zero. The number of iterations will correspond to the number of decimal digits. Assuming that you expect to get 0 digits in a zero value:
|
|||||||||||||||||||||
|
|
You can do:
This avoids any computationally expensive functions such as log or even multiplication or division. While it is inelegant this can be hidden by encapsulating it into a function. It isn't complex or difficult to maintain so I would not dismiss this approach on account of poor coding practice; I feel to do so would be throwing the baby out with the bath water. |
|||||||||||||||||||||
|
|
Constant-cost version that uses x86 assembly and a lookup table:
Another one, with a smaller lookup table and a log10 approximation taken from here.
Both of these take advantage of the fact that on x86 -INT_MIN is equal to INT_MIN. Update: As per suggestion here are the timings for the count_bsr and a slightly faster 64-bit only count_bsr_mod routines compared to the binary search and binary chop algos using very nice paxdiablo's test program modified to generate sets with a random sign distribution. Tests were built with gcc 4.9.2 using "-O3 -falign-functions=16 -falign-jumps=16 -march=corei7-avx" options and executed on an otherwise quiescent Sandy Bridge system with turbo and sleep states off. Time for bsr mod: 270000 Time for bsr: 340000 Time for binary chop: 800000 Time for binary search: 770000 Time for binary search mod: 470000 Source for the test,
|
||||
|
From Bit Twiddling Hacks : Find integer log base 10 of an integer the obvious way Note the ordering of comparisons in it. |
||||
|
|
|
Here is an unrolled binary search without any division or multiplication. Depending on the distribution of numbers given to it, it may or may not beat the other ones done with unrolled if statements, but should always beat the ones that use loops and multiplication/division/log10. With a uniform distribution of random numbers encompassing the whole range, on my machine it averaged 79% of the execution time of paxdiablo's count_bchop(), 88% the time of count_ifs(), and 97% of the time of count_revifs(). With an exponential distribution (the probability of a number having n digits is equal to the that of it having m digits, where m ≠ n) count_ifs() and count_revifs() both beat my function. I'm not sure why at this point.
|
|||||||||||||||||
|
|
I stumbled across this during a google search: http://www.hackersdelight.org/hdcodetxt/ilog.c.txt A quick benchmark clearly showed the binary search methods winning. lakshmanaraj's code is quite good, Alexander Korobka's is ~30% faster, Deadcode's is a tiny bit faster still (~10%), but I found the following tricks from the above link give a further 10% improvement.
Note this is log 10, not number of digits, so Doesn't support negatives, but that's easily fixed with a |
||||
|
|
|
|||||||||||||||||||||
|
Very inelegant. But quicker than all the other solutions. Integer Division and FP logs are expensive to do. If performance isn't an issue, the log10 solution is my favorite. |
|||||||||||||||||||||
|
|
Just a little adjust for C language:
|
|||
|
|
|
DON'T use floor(log10(...)). These are floating-point functions, and slow ones, to add. I believe the fastest way would be this function:
Note that the binary search version some people suggested could be slower due to branch mispredictions. EDIT: I did some testing, and got some really interesting results. I timed my function together with all the functions tested by Pax, AND the binary search function given by lakshmanaraj. The testing is done by the following code snippet:
Where the numbers[] array contains randomly generated numbers over the entire range of the int type (barring MIN_INT). The testing was repeated for each tested function on THE SAME numbers[] array. The entire test was made 10 times, with results averaged over all passes. The code was compiled with GCC 4.3.2 with -O3 optimization level. Here are the results:
I must say I got really astonished. The binary search performed far better than I thought it would. I checked out how GCC compiled this code to asm. O_O. Now THIS is impressive. It got optimized much better than I thought possible, avoiding most branches in really clever ways. No wonder it is FAST. |
|||||||||||||||||||||
|
|
you can find number of digits in a number by using this formaula ceil (log10 (abs (x))) where ceil returns a integer number just greater than number |
|||
|
|
|
I guess, the simplest way would be:
digits gives the answer. |
|||||
|
|
A simple way to find the length (i.e number of digits) of signed integer is this:
Where The call on |
||||
|
|
|
||||
|
|