Fast integer to decimal conversion

Question

Given an (unsigned) integer, what is the generally fastest way to convert it into a string that contains its decimal representation?

The naïve way of doing that is repeatedly dividing by 10, until you reach zero. I dislike this approach, because it

uses integer division, which is both slow and not available on some integrated platforms
requires the programmer to flip the string afterwards. This doubles the number of memory operations needed.

I thought of the following method to convert integers to decimal base. Is this a good idea? How is this done in common implementations of functions like printf ?

#include <stdint.h>

const static uint64_t i64_tab[20] = {
                     1u,
                    10u,
                   100u,
                  1000u,
                 10000u,
                100000u, /* 10^ 5 */
               1000000u,
              10000000u,
             100000000u,
            1000000000u,
           10000000000u, /* 10^10 */
          100000000000u,
         1000000000000u,
        10000000000000u,
       100000000000000u,
      1000000000000000u, /* 10^15 */
     10000000000000000u,
    100000000000000000u,
   1000000000000000000u,
  10000000000000000000u  /* 10^19 */
};

void uint64_to_string(char *out, uint64_t in) {
  int i;
  uint64_t tenpow;
  char accum;

  for (i = 19;i > 0;i--) {
    if (in >= i64_tab[i]) break;
  }

  do {
    tenpow = i64_tab[i];
    accum = '0';

    while (in >= tenpow) {
      in -= tenpow;
      accum++;
    }

    *out++ = accum;

  } while (i --> 0);

  *out = '\0';
}

const static uint32_t i32_tab[10] = {
           1u,
          10u,
         100u,
        1000u,
       10000u,
      100000u, /* 10^ 5 */
     1000000u,
    10000000u,
   100000000u,
  1000000000u, /* 10^9  */
};

void uint32_to_string(char *out, uint32_t in) {
  int i;
  uint32_t tenpow;
  char accum;

  for (i = 9;i > 0;i--)
    if (in >= i32_tab[i]) break;

  do {
    tenpow = i32_tab[i];
    accum = '0';

    while (in >= tenpow) {
      in -= tenpow;
      accum++;
    }

    *out++ = accum;

  } while (i --> 0);

  *out = '\0';
}

"Given an (unsigned) integer, what is the generally fastest way to convert it into an integer?" Do you mean if you start with a string? Because the fastest way to convert an integer to an integer is to do nothing :) — Justin, May 07 '12 at 20:18
@Seth No problem. I just kind of dislike "Just use X, I don't care nor know who it works though" — fuz, May 07 '12 at 20:20
@FUZxxl it depends on what you mean by 'fast' though. If you are actually wanting to get something done, using a built-in function is fastest. So I thought I'd answer it that way (though this isn't C++ which I didn't know at the time). No harm meant. — Seth Carnegie, May 07 '12 at 20:26
@Seth I'm not angry at you. Sorry if my comment was rude. It may be caused by my lack of knowledge of the libc, but it appears that I did not found such a function, except `sprintf`, which carries a big overhead because it needs to interpret the format string first. It's kind of funny, that I found over 4 functions to archieve the opposite effect (string to int). It seems people do not often need to write decimal numbers out. — fuz, May 07 '12 at 20:30
Closely related: [A C++ version of this same question](http://stackoverflow.com/questions/4351371/c-performance-challenge-integer-to-stdstring-conversion) — Ben Voigt, May 07 '12 at 20:37
I think this is the fastest way. 28 clocks on my Hazwell i7 box running a test loop from LONG_MIN to LONG_MAX - if you can live with signed output. My code's core runs all in unsigned space though, so easy to modify if not. http://stackoverflow.com/questions/21501815/optimal-base-10-only-itoa-function — , Nov 12 '14 at 00:45

score 2 · Answer 1 · answered May 07 '12 at 20:35

2

I believe integer division by a constant is as fast as doing a multiplication because the compiler optimizes integer division to integer multiplication for constant divisors. This is a heavy duty math trick performed by most optimizing compilers.

answered May 07 '12 at 20:35

usr

168,620
35
240
369

1

Integer multiplication is still pretty slow because it is a non-pipelined, microcoded operation, which means the entire OOO pipeline stops dead while it is executing. See the "Intel® 64 and IA-32 Architectures Optimization Reference Manual" for x86; I can tell you from experience that it's even worse on PPC. – Crashworks May 07 '12 at 20:42
@Crashworks, I don't have experience with this and I respect yours. This is very surprising. What about top-notch CPUs like Core i7? They *must* pipeline muls? – usr May 07 '12 at 20:49
@usr I am not familiar with this optimization. Do you have a reference? The only thing I can think of is to use modular inverse, but that would only work for odd numbers. – vhallac May 07 '12 at 20:58
@BenVoigt Isn't that for modular multiplication? – vhallac May 07 '12 at 21:00
3

http://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html This blog post series is excellent. I read it a few days ago. – usr May 07 '12 at 21:01
@vhallac Yes, all computer integer arithmetic is modular (over 2^32 or 2^64, natch). I didn't believe this answer at first until I looked at my compiler's output and it really does emit a multiplicative inverse. usr: That guide *is* for the modern i7s, I believe. Integer multiplication is very hard to fit in a pipeline because it has so many gate delays (http://bit.ly/JQRyeY). Also, many CPUs implement it as an iterative algorithm on one partial-product adder unit, which means it's microcoded and also not a constant number of steps. – Crashworks May 07 '12 at 21:18

score 2 · Accepted Answer · edited May 23 '17 at 11:54

The fastest approach on all but the simplest (e.g. 8-bit) microcontrollers is to use division, but reduce the number of divisions by generating several digits at once.

You will find very highly optimized code in answers to my question here. Using it in C should be a trivial edit to eliminate std::string -- there are no C++ features used in the actual conversion. The core is

while(val>=100)
{
   int pos = val % 100;
   val /= 100;
   *(short*)(c-1)=*(short*)(digit_pairs+2*pos); // or use memcpy
   c-=2;
}
while(val>0)
{
    *c--='0' + (val % 10);
    val /= 10;
}

I also provided an optimized division-free code for 8-bit micros, similar to the idea shown in the code in the question, but without loops. It ends up with a lot of code like this:

    if (val >= 80) {
        ch |= '8';
        val -= 80;
    }
    else if (val >= 40) {
        ch |= '4';
        val -= 40;
    }
    if (val >= 20) {
        ch |= '2';
        val -= 20;
    }
    if (val >= 10) {
        ch |= '1';
        val -= 10;
    }

That is interesting. I'm going to write a program to compare this approach to mine. — fuz, May 07 '12 at 21:08
@FUZxxl: I suggest you click through to that other question. Lots of code already, with performance data, and the benchmark code needed to do your own tests. — Ben Voigt, May 07 '12 at 21:09

score 1 · Answer 3 · answered May 07 '12 at 20:37

1

The generally fastest way is to index into a big enough array of pointers to strings. One array lookup, one pointer dereference. It's heavy on memory usage, though... That's the nature of engineering tradeoffs. How fast is fast enough?

answered May 07 '12 at 20:37

Jens

69,818
15
125
179

There is no "fast enough". What ever performs best is "fast enough" – fuz May 07 '12 at 20:45
1

Yes, there is a "fast enough", because what performs best is usually unattainable due to exorbitant resource requirements. My answer is the best example. Do you have enough memory for 2**64 pointers and the associated strings? Probably not. But I'm pretty confident that this performs best. – Jens May 07 '12 at 20:50
1

Nice counter-argument. On virtually all machines, a memory access is horrobly slow if not cached. It might thereby be an advantage to minimize the number of memory accesses done. – fuz May 07 '12 at 20:52

score 1 · Answer 4 · answered May 07 '12 at 20:47

The MS version of printf does it the "naïve" way (after setting up a bunch of variables based on the optional flags):

            while (precision-- > 0 || number != 0) {
                digit = (int)(number % radix) + '0';
                number /= radix;                /* reduce number */
                if (digit > '9') {
                    /* a hex digit, make it a letter */
                    digit += hexadd;
                }
                *text.sz-- = (char)digit;       /* store the digit */
            }

Fast integer to decimal conversion

4 Answers4

Linked