Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.
share|improve this question
    
Welcome to cs.SE! This looks like a "hard" question. If you do not get an answer in the next few days, please flag your question so we can discuss whether to migrate it to cstheory.SE (if they want it). –  Raphael Jul 23 '12 at 7:44
1  
I considered posting this to cstheory originally, but it didn't seem to be really that theory-oriented to me. I'm looking for a clever bit encoding, not exploring the theory of number representation, but if you think I'll have better luck there, I'm OK with being transferred. I also didn't post on stack overflow because I'm not really looking for a programming solution either, just a pragmatic encoding strategy. CS.SE seemed like the best fit to me. –  user35941 Jul 25 '12 at 14:41
    
I see. I am no expert in coding theory myself so I don't know how hard/theoretic the question really is. –  Raphael Jul 25 '12 at 15:31
1  
What do you want from your representation? Saying you want to "represent the golden ratio base more efficiently in binary" is not meaningful on it's own (you don't compress numbers - but you might compress some numbers). This looks more like you are sharing information about representations. If you want an actual answer, I would suggest mentioning what you want from your representation: does it need a particular form of addition? multiplication? do you need to use a particular algorithm to translate to decimal? Note: your rep is not a golden ratio base. It's based loosely on it. Thus? –  ex0du5 Jul 25 '12 at 21:25
1  
And just to be clearer. A completely valid answer to your "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" is: 0=0, 1=1, 10=2, 11=3, 100=4, ... That completely encodes an answer. Now why would that be a poor answer to you? Be specific. –  ex0du5 Jul 25 '12 at 21:29
show 1 more comment

2 Answers

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.

share|improve this answer
add comment

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).

share|improve this answer
    
I don't understand your system. What is the desired result of the process you describe? What does "~" mean at the end of the numbers? –  Raphael Nov 20 '12 at 9:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.