4 ms·
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 th
by openasocket 5y ago
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/ 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.
- failwhaleshark 5y agoYou'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.
- kwillets 5y agoIt'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.
- a1369209993 5y ago> 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