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.
ex0du5 asked for some clarification of what I need from a binary representation:
- 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.
- 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.
- 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.
- I'm ignoring division and subtraction for now, but having algorithms for them would be a bonus.
- 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.