5 ms·
I don't understand this fully, but it seems complicated. The way I have in mind is the same way you'd separate out the digits in a decimal number, except you'd
by BurningFrog 10y ago
I don't understand this fully, but it seems complicated.
The way I have in mind is the same way you'd separate out the digits in a decimal number, except you'd use 3 instead of 10 in the math.
- inimino 10y agoGP's suggestion is that you use 4 instead of 3. If you have 5 numbers, you multiply them by 4^5, 4^4, etc, and then add them. You waste some fractional bits, but you can do everything with masks and shifts instead of multiplications and divisions by three.
- kazinator 10y agoSuppose you have the ternary number "12102". We can encode each digit in two bits: 01,10,01,00,10 very easily. That gives us 0110010010, a ten bit number: a "binary coded ternary" whose value, in decimal, is 402. Now, we use that as an index into a table bct_value[402]. That table just looks up the numeric value of this code as an integer value in the range 0 to 242, which is also an 8 bit binary number: 146. That's our encoding of the five ternary digits in one byte. With the precomputed table, we just look up. We can also have a reverse table that takes 146 to 402, which we can break into groups of two bits and map to digits.
- BurningFrog 10y agoOK. That's the super optimized way to read the encoded data. Makes sense if performance is important. Writing is the harder part. I suppose you could just make 15 such tables, one for each possible value you could write.