How to convert from unbalanced to balanced ternary?

Question

My goal is to convert a decimal number into balanced ternary. Converting from decimal to unbalanced ternary simply requires division by 3 and keeping track of remainders. Once I have the unbalanced ternary representation of the number I can't seem to figure out how to "balance" it.

For example: 15 in decimal is 120 in unbalanced ternary and +--0 in balanced ternary. How do I go from 120 to +--0? I can't figure out how to deal with the 2s in the unbalanced ternary representation.

Thank you!

Hyaloid

Wikipedia has the answer. – Jarl

Does it really? I saw that portion in Wikipedia but I couldn't figure out what the T's meant. I think that method is pretty confusing, unless you're willing to explain it! – Hyaloid

For the balanced ternary notation, you're using + - and 0. Wikipedia uses 1 T and 0, respectively. And what exactly does Wikipedia say to do with the 2s? – Jarl

Thank you user3386109 :) – Hyaloid

So when it's adding the 2's that have been changed to 1T's, when it sees two 1's in the same place it turns them into a T as well? – Hyaloid

Yes, that's correct. You may have to go through several iterations changing 2's to 1T's. (I assume that you meant that last T to be a 1T). – Jarl

In the wikipedia example, they kind of skipped over the middle iteration. It should be `0212 = 0010 + 1T00 + 001T = 1T2T = 1T0T + 01T0 = 10TT – Jarl

That makes perfect sense, thanks again! – Hyaloid

Any time, glad to help :) – Jarl

Answer 1

Note that 2 in ternary is +- in balanced ternary, or in decimal 2 = 3 - 1. So if you start with an array filled with 0s, 1s, and 2s, just replace every 2 with a -1 and add 1 to the number to its left. (Make sure you have an extra 0 at the beginning of the number, at least if it starts with a 2.) Depending on how you do the replacement you may also need to replace 3s with 0s, adding 1 to the left as usual. Then repeat the process until there are no more 2s (or 3s).

Kanazawa

Answer 2

One way of seeing it is, if you are getting a remainder 2 with a remaining quotient of x, it is equivalent to getting a remainder of -1 with a remaining quotient of x+1.

Converting it then is like simple conversion to a ternary base, with one extra check.

String output="";
while (n>0) {
   rem = n%3;
   n = n/3;
   if (rem == 2) {
       rem = -1;
       n++;
   }
   output = (rem==0?'0':(rem==1)?'+':'-') + output;
}

The running program can be found here.

Coincidentally

Answer 3

Because I was missing this in the internet, here my own timplementation in Pari/GP -

{balanced_ternary(x,maxdigits=20,chars=["y","0","1"])=my(res,st,dez,dig);
      dez=floor(log(abs(2*x))/log(3)); 
      res=x/3^dez;
      st=""; 
      for(k=0,maxdigits,
               if(k==dez+1,st=Str(st,"."));
               dig = if(res>1/2 
                       ,res--;chars[2+1]
                       ,if(res<-1/2
                              ,res++;chars[2-1]
                              ,chars[2+0]
                 )); 
               st=Str(st,dig);res*=3
           );
       return(st);}

Then

balancedternary (1)    \\ %1002 = "1.00000000000000000000"
balancedternary (-1)   \\ %1003 = "y.00000000000000000000"
balancedternary (1.2)  \\ %1004 = "1.1yy11yy11yy11yy11yy1"
balancedternary (-1.2) \\ %1005 = "y.y11yy11yy11yy11yy11y"

balancedternary (27-3) \\ %1006 = "10y0.00000000000000000"
balancedternary (400)  \\ %1007 = "1yy0y11.00000000000000"
balancedternary (sqrt(3))   \\ %1008 = "1y.y1yy10y0000yy1100y0"
balancedternary (sqrt(3)/3) \\ %1009 = "1.yy1yy10y0000yy1100y0"

Just q&d, not all "special cases" checked/coded.

Link

Answer 4

I know this question is about conversion from regular ternary, but FWIW, you can also achieve your stated goal by going straight from decimal into balanced ternary, e.g. via the programs at

• Balanced ternary - Rosetta Code
• Balanced Ternary Converter - Code Golf Stack Exchange

Radioscope

Answer 5

Biased Ternary vs. Balanced Ternary

The Ternary Manifesto by Douglas W. Jones is an excellent source of information on the topic of (balanced) ternary representation. The author notes that

balanced ternary encoding is exactly equivalent to a biased encoding

Biased encoding is a way to encode signed numbers in (bounded) unsigned numbers using an offset b. To read a biased number, read it as usual, then subtract b to get the represented value.

Douglas W. Jones describes the connection between ternary biased and balanced numbers as follows, giving an example with two ternary digits (= trits).

Decimal  Biased Balanced
   4       22      ++
   3       21      +0
   2       20      +-
   1       12      0+
   0       11      00
  -1       10      0-
  -2       02      -+
  -3       01      -0
  -4       00      --

[...]
the natural bias b for an n-trit ternary number is all ones:
b = ⌊3ⁿ / 2⌋ = (3ⁿ-1) / 2
[...]
To convert biased numbers to balanced numbers, subtract 1 from each digit, so 2 becomes +1 (represented as +), 1 becomes 0 (represented as 0), and 0 becomes –1 (represented as -).
[...]
This is merely a change of the symbols associated with the digits, a matter of how the digits are printed on the page, not a matter of how the digits are represented inside some mechanism. The difference between biased and balanced representations can be considered to be entirely cosmetic

Converting Integers to Balanced Ternary

To convert an integer i to balanced ternary

• Compute n, the number of digits in i's balanced ternary representation.
  By solving |i| ≤ (3ⁿ-1) / 2 for n we know that n = ⌈log₃(2|x|+1)⌉.
• Compute the bias b = (3ⁿ-1) / 2.
• Then convert i+b to a ternary string with n digits (leading 0s are important!),
• and replace the characters 012 by -0+.

Example implementation in Java's jshell:

import static java.lang.Math.*;

String balTer(int i) {
  // n=…+1 and ….substring(1) ensure leading zeroes 
  int n = max(1, (int) ceil(log(2 * abs(i) + 1) / log(3))) + 1;
  int b = ((int) pow(3, n) - 1) / 2;
  return Integer.toString(i + b, 3).substring(1)
      .replace('0', '-').replace('1', '0').replace('2', '+');
}

balTer(15) // returns "+--0"

Ashia