Comment by openasocket | Hacker News Reader

Comment by openasocket | Hacker News Reader

Parent Full thread

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.

You'd need 128-bit integers because of the way this works in the intermediate steps before the shift. There are u128 types in many modern compilers, but it's probably cheaper just to use a different type (u64) of table and another operation.

> how easily this could be extended to 64 bit integers?

It's effectively:

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

Assembly can do (from a equivalent start):

  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

It's easier when there are more bits available than in the original operand.

For 64, a variable shift may work. Powers of 10 have a lot of trailing 0 bits.

Reply on news.ycombinator.com