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

Question

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 of the BTTS with as little difficulty as possible. One of the tricky aspects of this system is that carries happen in both directions, i.e.
$1 + 1 = 1 \bar 1 .1$ and $\bar 1 + \bar 1 = \bar 1 1.\bar 1$.

This is my first post here, so please let me know if I need to fix or clarify anything.

--Edit--

ex0du5 asked for some clarification of what I need from a binary representation:

1. I want to be able to represent positive values of both integers and powers of $\phi$. The range of representable values need not be as good as binary, but it should be better than phinary per bit. I want to represent the largest possible set of phinary numbers in the smallest amount of space possible. Space takes priority over operation count for arithmetic operations.
2. I need addition to function such that carries happen in both directions. Addition will be the most common operation for my application. Consequently it should require as few operations as possible. If a shorter sequence of operations are possible using a longer bit representation (conflicting with goal 1), then goal 1 takes priority. Space is more important than speed.
3. Multiplication only needs to handle integers > 0 multiplied to a phinary number, not arbitrary phinary number multiplication, and so can technically be emulated with a series of additions, though a faster algorithm would be helpful.
4. I'm ignoring division and subtraction for now, but having algorithms for them would be a bonus.
5. I need to eventually convert a phinary number to a binary floating point approximation of it's value, but this will happen only just prior to output. There will be no converting back and forth.

Answer 1

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.

Answer 2

The easiest way (assuming I understand your question - I was a very bored Year 10 graduate) is to go to base 2.618~ and use the following system: if initial bit = 0 then 0 if initial bit = 1 then see next bit. if next bit = 0 then 1 if next bit = 1 then 2

Advantages: uses space efficently. Uses 1.618~ bits per notation. Disadvantages: Hard to work with. (and slow).