Computing the number of digits of an integer even faster (lemire.me)

it all goes back to 650x, where we had no multiplication/division and we had to create sin/cos tables.

The big table becomes more obvious when the constants are written using hex:

  static uint64_t table[] = {
    0x100000000, 0x1FFFFFFF6, 0x1FFFFFFF6,
    0x1FFFFFFF6, 0x2FFFFFF9C, 0x2FFFFFF9C,
    0x2FFFFFF9C, 0x3FFFFFC18, 0x3FFFFFC18,
    0x3FFFFFC18, 0x4FFFFD8F0, 0x4FFFFD8F0,
    0x4FFFFD8F0, 0x4FFFFD8F0, 0x5FFFE7960,
    0x5FFFE7960, 0x5FFFE7960, 0x6FFF0BDC0,
    0x6FFF0BDC0, 0x6FFF0BDC0, 0x7FF676980,
    0x7FF676980, 0x7FF676980, 0x7FF676980,
    0x8FA0A1F00, 0x8FA0A1F00, 0x8FA0A1F00,
    0x9C4653600, 0x9C4653600, 0x9C4653600,
    0xA00000000, 0xA00000000,
  };

No way to leverage popcount instruction for this?

    x |= x >>  1;
    x |= x >>  2;
    x |= x >>  4;
    x |= x >>  8;
    x |= x >> 16;
    return popcount(x-1);

you can also base your solution on hamilton cycles. that also boils down to o(1).

This blog post is a response to another blog post which is a response to a question about how to implement integer-to-string length as quickly as possible in an optimising implementation of the Ruby programming language called TruffleRuby, if people here wanted a concrete example of how these kind of brain-teasers come up for real in industrial programming in an everyday job.

I sometimes have difficulty finding efficient algorithms for specific tasks like this. Any advice on becoming better at finding efficient algorithms?

    Digits = LEN( STR$( SomeNumber ))

(run and hide in shame)

Here's one interesting application of a digit-count function.

The naive implementation of an integer-to-string conversion involves writing the number backwards, starting from the least significant digit, and then reversing the string at the end.

In a 2017 talk titled "Fastware"[1], Andrei Alexandrescu showed that it's faster to start by counting the number of digits you're going to print, and then you can print by working backwards from the least significant digit. It comes out in the correct order without any need to reverse at the end.

His implementation of the digit count was itself interesting, since it does 4 comparisons per loop and then a divide by 10000, instead of the naive single comparison and divide by 10.

    uint32_t digits10(uint64_t v) {
      uint32_t result = 1;
      for (;;) {
        if (v < 10) return result;
        if (v < 100) return result + 1;
        if (v < 1000) return result + 2;
        if (v < 10000) return result + 3;
        v /= 10000U;
        result += 4;
      }
    }

IIRC, his insight was that smaller numbers tend to occur more often in the real world, so most calls to this function will not end up doing any divisions.

[1] https://www.youtube.com/watch?v=o4-CwDo2zpg

A few days ago I had to write a bit of code in C# with an int to string conversion, and since I never use that language and I'm not used to OOP I completely looked over the ToString() method every primitive type has, I wrote a dumb conversion like I used to do as a student in C. The basic modulo 10 loop thing. You know the one.

Anyway I'm glad to know there's a cool lookup table trick out there, I never really get to use anything like that but it makes for a nice read.

Awesome find! But I wonder how easily this could be extended to 64 bit integers? That sequence in the lookup table won't fit into 64 bits if it's extended. I think you would have to fall back to just having the lookup table storing the transition data, as described in https://commaok.xyz/post/lookup_tables/ in the "A Small Step" section. And probably add a conditional in the beginning to handle very large integers that would overflow. Alternatively you might be able to do something with two lookup tables, but I think at that point you've got enough lookup data that it would be less efficient.

  size_t logx = int_log2(x);
  uint32_t carry = ((uint64_t)x + tablo[logx]) >> 32;
  return tabhi[logx] + carry;

  mov rdx rax  # save x
  xor eax eax
  add rdx [8*rcx+tablo]  # set carry (would cmp be better?)
  adc al [1*rcx+tabhi]  # result never exceeds 64/log(10) < 20

I recall needing this on a snprintf() implementation.

Isn't this effectively a table-optimized logBase(x) rounded-up to the ceiling, which can be reduced to efficient log2(x)/log2(Base)? If you know the base, then you can combine many ops into table-lookups.

As an exercise to the reader, I suggest creating efficient code constrained to 32-bit or 16-bit unsigned.

PS: I was going to say "look at Hacker's Delight." I can definitely read. LOL.

It'd be interesting to see a performance benchmark of the various solutions, including ones that don't use lookup tables.

The results of such a benchmark would probably heavily depend on whether the lookup table is allowed to be in the CPU caches.

This is a fun optimization, but what is a use case where I would need to count the number of digits?

Is there a version of this that would tell you the number of bytes an integer would use? If so, how would it differ with signed versus unsigned integers?