0

There's two methods I've read about, divide by 10 repeatedly (or slightly more efficiently, divide in a way to minimize division operations) i.e. 

int getFirstDigit(unsigned int num) {
    if (num >= 100000000)
        num /= 100000000;
    if (num >= 10000)
        num /= 10000;
    if (num >= 100)
        num /= 100;
    if (num >= 10)
        num /= 10;

    return num;
}

Credit: How to retrieve the first decimal digit of number efficiently

With an unsigned int, this will at most divide 3 times, reducing division operations which are as far as I know, the most expensive assembly operation. My question is, how does that compare to the following string operation:

int getFirstDigit(unsigned int num) {
    return (to_string(num))[0] - '0';
}

It converts to string, gets the character, and offsets by 48 to get the pure number the character would represent. I do know strings are associated with tremendous amounts of overhead, and I did a bit of looking around, but I couldn't find a concrete answer comparing the two.

Afterthought: I saw a log in the page I credited earlier, and I suppose I could take the log base 10 of the number, floor the result to see what order of 10 it is bound from below by, and use that number as the exponent for 10 where they divide the number I'm looking at, reducing it to a log operation, power operation, and division operation. If that's even reducing it. But again, I have no idea the relative run times.

Sorry in advance, I did see a lot of similar questions, but none that I felt answered my specific question of relative run times based on efficiency at the assembly level. My gut tells me the division is far better than string but I can't feel certain because a string is just contiguous ascii values in memory.

Kosba2
  • 15
  • 6
  • 1
    why don't you benchmark? also, have you actually measured a performance problem? Or are you prematurely optimizing? – Mitch Wheat Nov 05 '18 at 23:27
  • I ask as a curiosity rather than a necessity to optimize. I've benchmarked by timing the operations but the answer was not satisfying, was hoping to get a broader more concrete answer rather than just following the results of what felt like an unreliable test. – Kosba2 Nov 05 '18 at 23:34
  • The MSVC compiler (preview) just got a major upgrade for the `to_chars()` function which converts floats and doubles to strings and runs with over an order of magnitude increase in speed. https://twitter.com/blelbach/status/1045471749641367552 While not likely to outperform the test/divide sequence in the question it's amazingly fast. – doug Nov 06 '18 at 00:01

1 Answers1

0

Short answer: no-one knows until you profile (benchmark) your code!

Longer answer: modulo + division should be faster than any version involving string converstion but there are exceptions: absent any built-in hardware support, any itoa/to_string implementation needs to perform the same relatively expensive modulo and division you're already performing by necessity (as you're converting from one base to another) in addition to string allocation, so therefore doing only the modulo and division operations should be faster.

This does depend on your platform - if you're using Java or C# then your runtime (the JVM and CLR respectively) implement the ToString operation internally using heavily optimized platform-specific code which will likely be faster than doing the arithmetic yourself even though their version includes string allocation.

Dai
  • 141,631
  • 28
  • 261
  • 374
  • Thanks for the breakdown! I ask despite the test I ran because it didn't feel reliable. There's no particular code context I need it for, just wanted to figure out where string lies in the hierarchy of operations. Just to be clear, when you guys tell me to benchmark it, I'm assuming you mean to check the run time of the operations in question? – Kosba2 Nov 05 '18 at 23:39
  • @Kosba2 Correct. Write some code that uses high-resolution timers (e.g. performance-counters) that runs your code 100,000 times and compare that to other approaches 100,000 times. Also, see this: https://stackoverflow.com/questions/1235371/fastest-base-conversion-method – Dai Nov 06 '18 at 00:01