Minimise bit wizardry

[interrealm]

1.5 bits is not enough to store a ternary value as claimed. Instead, it would be log_2(3) bits, or approximately 1.58496250072 bits.

[interrealm]

FYI: 1.5 bits would only be able to store approximately 2.82842712 states

[james-cnz]

Yup, looking into this, 1.6 bits per variable seems like the best option (8 bits per 5 variables).

I think it's probably best to group the variables into blocks with lengths of a power of 2 bits, or at least multiples of 8 bits, so there's some memory alignment. Without grouping the variables together, we require 2 bits to store 1 variable. 4 bits can only stores 2 variables, so there's no compression advantage. 8 bit can store 5 variables, so this is an improvement. If we only look at whole numbers of bytes, then I think the next improvement in compression doesn't come until 176 bits (22 bytes), which I don't think is practical.

[TodePond]

1.5 is fine because booleans always get stored in pairs

[james-cnz]

Not sure I understand. Two 3-state bools would have a combined total of 3x3 = 9 possible states. Just too many to fit in 3 bits.

[TodePond]

You have to re-order them to fit in all the possibilities

[james-cnz]

I think rearranging to fit more in can work with infinite numbers, like in Hilbert's paradox of the Grand Hotel. I'm pretty sure it doesn't work with finite numbers though.

[TodePond]

It works in this case. Sorry I don't do philosophy x

[james-cnz]

Ah well. It's been some time since I was at uni. Perhaps I forget.

[wendyn-projects]

I am confused on how to store 2 trileans in 3 bits, since you can story only 8 values in 3 bits but 2 trileans can represent 9 different values:

00,  01,  0T,  10,  11,  1T,  T0,  T1,  TT
000, 001, 010, 011, 100, 101, 110, 111, 😭

[TodePond]

You have to re-order them to fit in all the possibilities

[wendyn-projects]

Oh, I think I understand, you also need to keep an information about the order of the trileans somewhere and whenever one bit changes, you will need to change order accordingly, so when you have two 3 value booleans a, b, you need six 3bit values and order of a, b:

bits, value, order0, order1
000   FF     a, b    b, a
001   MM     a, b    b, a
010   TT     a, b    b, a
100   FM     a, b    b, a
101   MT     a, b    b, a
110   TF     a, b    b, a

I could use 4 bits and be done with my boolean implementation, but that seems kinda wasteful. Would it be possible to find even more efficient method to store one 6 state value and one 2 state value? If it was 9 states, like I originally thought, I could just use Densely Packed Decimal but looking at how easy this solution is to decode I understand the performance benefits.

   1XX order0 |    0XX orderX |    1XX order1 |    0XX orderX
FF --> FM     | FM --> FF     | FF --> MF     | MF --> FF
MM --> MT     | MT --> MM     | MM --> TM     | TM --> MM
TT --> TF     | TF --> TT     | TT --> FT     | FT --> TT

   1-- order1      0-- order0 |    1-- order1 |    0-- order0
FM --> FT     | FT --> FM     | FM --> TM     | TM --> FM
MT --> MF     | MF --> MT     | MT --> FT     | FT --> MT
TF --> TM     | TM --> TF     | TF --> MF     | MF --> TF