What is a good binary encoding for $\phi$-based balanced ternary arithmetic algorithms?

I've been looking for a way to represent the golden ratio ($\phi$) base more efficiently in binary. The standard binary golden ratio notation works but is horribly space inefficient. The Balanced Ternary Tau System (BTTS) is the best I've found but is quite obscure. The paper describing it in detail is A. Stakhov, Brousentsov's Ternary Principle, Bergman's Number System and Ternary Mirror-symmetrical Arithmetic, 2002. It is covered in less depth by this blog post.

BTTS is a balanced ternary representation that uses $\phi^2 = \phi + 1$ as a base and 3 values of $\bar 1$ ($-1$), $0$, and $1$ to represent addition or subtraction of powers of $\phi^2$. The table on page 6 of the paper lists integer values from 0 up to 10, and it can represent any $\phi$-based number as well.

BTTS has some fascinating properties, but being ternary, I didn't think I'd be able to find a compact bit representation for it.

Then I noticed that because of the arithmetic rules, the pattern $\bar 1 \bar 1$ never occurs as long as you only allow numbers $\ge 0$. This means that the nine possible combinations for each pair of trits ($3^2$) only ever has 8 values, so we can encode 2 trits with 3 bits ($2^3$, a.k.a octal). Also note that the left-most bit (and also right-most for integers because of the mirror-symmetric property) will only ever be $0$ or $1$ (again for positive numbers only), which lets us encode the left-most trit with only 1 bit.

So a $2^n$-bit number can store $\lfloor 2^n/3\rfloor * 2 + 1$ balanced trits, possibly with a bit left over (maybe a good candidate for a sign bit). For example, we can represent $10 + 1 = 11$ balanced trits with $15 + 1 = 16$ bits, or $20 + 1 = 21$ balanced trits with $30 + 1 = 31$ bits, with 1 left over (32-bit). This has much better space density than ordinary golden ratio base binary encoding.

So my question is, what would be a good octal (3-bit) encoding of trit pairs such that we can implement the addition and other arithmetic rules

I'm going to try to answer this myself, in the hope that my answer will give others a better idea of what I'm after and lead to better answers than mine.

I found that framing the problem in terms of the original golden ratio base helped me to think about a binary encoding more effectively. I want to note however that there is no difference between BTTS and phinary except the length of the representation. Both number systems represent the same set of numbers, save that BTTS more easily encodes negative numbers. Just as 3 bits can theoretically represent 2 trits of BTTS, they should also be able to represent 4 bits of phinary (which is what 2 trits encode). Keep in mind that in standard base-$\phi$ all instances of $011_\phi$ are replaced with $100_\phi$ and $1_\phi + 1_\phi = 10.01_\phi$, with a carry both one place to the left and two to the right. The following table is my best attempt thus far:

Phinary  |  Binary | Octal
0 0 0 0  |  0 0 0  |   0
0 0 0 1  |  0 0 1  |   1
0 0 1 0  |  0 1 0  |   2
0 1 0 0  |  0 1 1  |   3
0 1 0 1  |  1 0 0  |   4
1 0 0 0  |  1 0 1  |   5
1 0 0 1  |  1 1 0  |   6
1 0 1 0  |  1 1 1  |   7

There are some benefits to this encoding. One is that $0_\phi$ and $1_\phi$ are the same as for binary. Another is that a carry in the forward direction works as expected automatically:

$1010_\phi + 1_\phi = 1011_\phi = 1100_\phi = 1\ 0000_\phi$, and $111_2 + 1_2 = 1\ 000_2$.

Another advantage is that addition almost works as is:

$0101_\phi + 0010_\phi = 0111_\phi = 1001_\phi$ and $100_2 + 010_2 = 110_2$.

As far as I can tell, the only places addition breaks down are for $2_8 + 2_8$, $5_8 + 7_8$ and $7_8 + 7_8$.

$0010_\phi + 0010_\phi = 0020_\phi = 0100.1_\phi$, not $0101_\phi$.

$1000_\phi + 1010_\phi = 2010_\phi = 1\ 0020_\phi = 1\ 0100.1_\phi$, not $1\ 0101_\phi$.

$1010_\phi + 1010_\phi = 2020_\phi = 2100.1_\phi = 1\ 1000.1_\phi$, not $1\ 1001_\phi$.

All other additions work (excluding right carry logic).

We can handle right carries by looking at how they are produced. I'll be using octal for brevity.

• 1, 4, and 6 produce a right carry of 3 to the previous 3 bits when they are added to themselves or each other.

• 2 and 7 produce a right carry of 5 added to the previous 3 bits when added to themselves or each other.

• 4 + 3 gives a right carry of 3 and 5 + 7 gives a right carry of 5.

That's all we need to check for (I think) with the exception of also testing for 2 + 2, 5 + 7, and 7 + 7 and subtracting 1 from the result.

So basically we are taking advantage of the redundancy in a 4-bit phinary representation ($011_\phi = 100_\phi$) to represent the same numbers without redundant cases in 3-bits of binary.

A $2^n$ bit number can store $\lfloor 2^n / 3\rfloor * 4 + 1$ phinary bits.

I'm sure there are clever bit-hacky ways to do this better, but I'm hoping that this will clarify my intent and provide a starting point for both myself and anyone else wanting to tackle this.

StackExchange Computer Science Q#2847, answer score: 2