3 ms·
Since 3⁵ (243) is less than 256, you can actually fit 5 "trinary" numbers into a byte. The code gets more complex and slow, but not really by much.
by BurningFrog 10y ago
Since 3⁵ (243) is less than 256, you can actually fit 5 "trinary" numbers into a byte.
The code gets more complex and slow, but not really by much.
- kosma 10y agoUnless you're optimizing for raw speed, converting from/to base-3 using your language's standard library should be short and sweet.
- inimino 10y agoThat would give you a string, right? Are you suggesting something like concatenating five numbers into a string first?
- bill45 10y agoThere's actually an optimal way to pack them in without guessing the base you need: https://codeplea.com/optimal-bit-packing https://codeplea.com/optimal-bit-packing
- kazinator 10y agoJust table lookup. The word is "ternary", by the way. A useful intermediate representation would be "binary coded ternary" (BCT?) whereby 121 gets represented as 011001. The code 11 isn't used, just like 1010 through 1111 are not used in binary-coded decimal (BCD). The 10 bit BCT representation of a five digit ternary number could index into an array of 1024 entries, each yielding its numeric value, that fits into a byte. Likewise, a reverse table of 243 values can map to a 10 bit BCT. Conversions between BCT and textual digits are trivial.
- BurningFrog 10y agoI 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.