Binary to ternary representation convertion

Question

Hi,

Does anybody know (or may point to some source to read about) a method or algorithm to convert a number represented in binary numeral system into the ternary one (my particular case), or universal algorithm for such conversions?

The solution I've already implemented is to convert a number to decimal first and then convert it into required numeral system. This works, but there are two steps. I wonder if it could be done in one step easily without implementing ternary arithmetic first? Is there some trick, guys?

UPD: It seems I didn't manage to describe clearly which way of conversion I'm looking for. I'm not asking for some way to convert base-2 to base-3, I do know how to do this. You may consider that I have algebraic data structures for ternary and binary numbers, in Haskell it looks like this:

data BDigit = B0 | B1
type BNumber = [BDigit]

data TDigit = T0 | T1 | T2
type TNumber = [TDigit]

And there are two obvious ways to convert one to another: first is to convert it into Integer first and get the result (not interesting way), second is to implement own multiplication and addition in base-3 and compute the result multiplying digit values to respective power of two (straightforward and heavy).

So I'm wondering if there's another method than these two.

Answer 1

If you find a match where 2^m and 3^n are the same number, then you could create a table with replacements.

So, for example (is not valid, but for illustration:)
0000 = aaa
0001 = aab
0010 = aac ....

You see how it goes?

Answer 2

If you are doing it with a computer things are already in binary, so just repeatedly dividing by 3 and taking remainders is about as easy as things get.

If you are doing it by hand, long division in binary works just like long division in decimal. just divide by three and take remainders. if we start with 16

   ___101
11 |10000
     11
      100
       11
        1   

100000 / 11 = 101 + 1/11 so the least significnnt digit is 1

101/ 11 = 1 + 10/11  the next digit is 2

1  and the msd is 1

so in ternary 121

Answer 3

In case this is homework, pseudocode to write x in base b backwards:

while (x != 0) {
    q <-- x/b
    r <-- x - q*b
    print r
    x <-- q
}

I'm sure you can figure out how to write the result forwards instead of backwards. Note that / needs to be C-style integer division (the result is an integer, truncated toward zero).

Note that this doesn't depend at all on the base that the arithmetic is performed in. Arithmetic is defined on integers, not the representation of integers in a specific base.

---

Edit: Based on your updated question, I would slam the digit representation into an integer (via ors and shifts) and use the algorithm described above with integer arithmetic.

Certainly you could do it as you describe, but it seems like an awful lot of work.

Answer 4

I don't think there's a super-efficient way.

"The solution I've already implemented is to convert a number to decimal first."

I assume that you are actually converting to some built-in integer type first. I don't think that built-in integer has anything to do with base 10. (Though, when you print it, there will be a base 10 conversion).

Maybe you'd expect there to be some algorithm which looks at the input one digit at a time and produces the output.

But, say you want to convert 3486784400 (base 10) to base 3. You'll need to examine every digit before producing output, because

3486784401 (base 10) = 100000000000000000000 (base 3)
3486784400 (base 10) =  22222222222222222222 (base 3)

..also

"compute the result multiplying digit values to respective power of two"

explicitly computing a power isn't necessary, see http://stackoverflow.com/questions/3358662/convert-from-base-60-to-base-10

Answer 5

I think there might be some different different "views" of the problem, though I'm not sure any of them are faster or better. For example, the lower order base 3 digit of n is just n mod 3. Let say you already have the binary representation of n. Then consider how the powers of 2 work out mod 3. 2^0 = 1 mod 3, 2^1 = 2 mod 3, 2^2 = 1 mod 3, 2^3 = 2 mod 3, ... In other words, the powers alternate between being 1 mod 3 and being 2 mod 3. You now have an easy way to get the low-order base 3 digit by scanning the binary representation of n and usually only addition of either 1 or 2 at each bit position where a 1 occurs.

Answer 6

You can use some clever abbreviations for converting. The following code is the "wrong" direction, it is a conversion from ternary to binary based on the fact that 3^2 = 2^3 + 1 using only binary addition. Basically I'm converting two ternary digits in three binary digits. From binary to ternary would be slightly more complicated, as ternary addition (and probably subtraction) would be required (working on that). I'm assuming the least significant digit in head of the list (which is the only way that makes sense), so you have to read the numbers "backwards".

addB :: BNumber → BNumber → BNumber
addB a [] = a
addB [] b = b
addB (B0:as) (B0:bs) = B0 : (addB as bs) 
addB (B0:as) (B1:bs) = B1 : (addB as bs)
addB (B1:as) (B0:bs) = B1 : (addB as bs)
addB (B1:as) (B1:bs) = B0 : (addB (addB as bs) [B1])

t2b :: TNumber → BNumber
t2b [] = []
t2b [T0] = [B0]
t2b [T1] = [B1]
t2b [T2] = [B0,B1]
t2b (T2:T2:ts) = let bs = t2b ts in addB bs (B0:B0:B0:(addB bs [B1]))
t2b (t0:t1:ts) = 
   let bs = t2b ts
       (b0,b1,b2) = conv t0 t1
   in addB bs (b0:b1:b2:bs) 
   where conv T0 T0 = (B0,B0,B0)
         conv T1 T0 = (B1,B0,B0)
         conv T2 T0 = (B0,B1,B0)
         conv T0 T1 = (B1,B1,B0)
         conv T1 T1 = (B0,B0,B1)
         conv T2 T1 = (B1,B0,B1)
         conv T0 T2 = (B0,B1,B1)
         conv T1 T2 = (B1,B1,B1)

[Edit] Here is the binary to ternary direction, as expected a little bit more lengthy:

addT :: TNumber → TNumber → TNumber
addT a [] = a
addT [] b = b
addT (T0:as) (T0:bs) = T0 : (addT as bs) 
addT (T1:as) (T0:bs) = T1 : (addT as bs)
addT (T2:as) (T0:bs) = T2 : (addT as bs)
addT (T0:as) (T1:bs) = T1 : (addT as bs) 
addT (T1:as) (T1:bs) = T2 : (addT as bs)
addT (T2:as) (T1:bs) = T0 : (addT (addT as bs) [T1])
addT (T0:as) (T2:bs) = T2 : (addT as bs)
addT (T1:as) (T2:bs) = T0 : (addT (addT as bs) [T1])
addT (T2:as) (T2:bs) = T1 : (addT (addT as bs) [T1])

subT :: TNumber → TNumber → TNumber
subT a [] = a
subT [] b = error "negative numbers supported"
subT (T0:as) (T0:bs) = T0 : (subT as bs) 
subT (T1:as) (T0:bs) = T1 : (subT as bs)
subT (T2:as) (T0:bs) = T2 : (subT as bs)
subT (T0:as) (T1:bs) = T2 : (subT as (addT bs [T1])) 
subT (T1:as) (T1:bs) = T0 : (subT as bs)
subT (T2:as) (T1:bs) = T1 : (subT as bs)
subT (T0:as) (T2:bs) = T1 : (subT as (addT bs [T1]))
subT (T1:as) (T2:bs) = T2 : (subT as (addT bs [T1]))
subT (T2:as) (T2:bs) = T0 : (subT as bs)

b2t :: BNumber → TNumber
b2t [] = []
b2t [B0] = [T0]
b2t [B1] = [T1]
b2t [B0,B1] = [T2]
b2t [B1,B1] = [T0,T1]
b2t (b0:b1:b2:bs) = 
   let ts = b2t bs
       (t0,t1) = conv b0 b1 b2
   in subT (t0:t1:ts) ts
   where conv B0 B0 B0 = (T0,T0)
         conv B1 B0 B0 = (T1,T0)
         conv B0 B1 B0 = (T2,T0)
         conv B1 B1 B0 = (T0,T1)
         conv B0 B0 B1 = (T1,T1)
         conv B1 B0 B1 = (T2,T1)
         conv B0 B1 B1 = (T0,T2)
         conv B1 B1 B1 = (T1,T2)

[Edit2] A slightly improved version of subT which doesn't need addT

subT :: TNumber →  TNumber →  TNumber
subT a [] = a
subT [] b = error "negative numbers supported"
subT (a:as) (b:bs) 
  | b ≡ T0 = a : (subT as bs)
  | a ≡ b =  T0 : (subT as bs)
  | a ≡ T2 ∧ b ≡ T1 =  T1 : (subT as bs)
  | otherwise = let td = if a ≡ T0 ∧ b ≡ T2 then T1 else T2 
                in td : (subT as $ addTDigit bs T1)  
    where addTDigit [] d = [d]
          addTDigit ts T0 =  ts
          addTDigit (T0:ts) d = d:ts 
          addTDigit (T1:ts) T1 = T2:ts
          addTDigit (t:ts) d = let td = if t ≡ T2 ∧ d ≡ T2 then T1 else T0
                               in td : (addTDigit ts T1)

Answer 7

I'm afraid I don't know enough Haskell to be able to express this in code but I wonder if using Horner's rule for evaluating polynomials might yield a method.

For example a*x^2 + b*x + c can be evaluated as c+x*(b+x*a).

To convert, say, the ternary number a*9+b*3+c to binary, one starts with the binary representation of a, then multiplies that by 3 (i.e shift and add), then adds the binary representation of b, multiplies the result by 3 and adds c.

It seems to me this should be doable with a map (to get the binary representation of the ternary digits) and a fold (of a,b -> a+3*b)

Answer 8

No, you can't convert a base2 number to a base3 number without loading it into an integer. The reason is that 2 and 3 are coprime - they have no common factors.

If you were working with base2 and base4, or even base6 and base9, then the set of integers up to the lowest common multiple of the two bases would be represented by two isomorphic sets. For example 13 (base4) = 0111 (base2), so converting 1313 (base4) = 01110111 (base2) - it's a find and replace operation.

At least the solution that you have works and is relatively simple. If you need to improve performance then convert the entire base2 representation to an integer before starting the base3 conversion; it means less modulus operations. The alternative would be process each character in the base2 number one by one, in which case you'll be dividing by all the powers of 3 for each digit in the base2 representation.

Answer 9

I think that everybody is missing something important. First, compute a table in advance, for each binary bit, we need the representation in ternary. In MATLAB, I'd built it like this, although every other step after that will be done purely by hand, the computation is so easy.

dec2base(2.^(0:10),3)
ans =
0000001
0000002
0000011
0000022
0000121
0001012
0002101
0011202
0100111
0200222
1101221

Now, consider the binary number 011000101 (which happens to be the decimal number 197, as we will find out later.) Extract the ternary representation for each binary bit from the table. I'll write out the corresponding rows.

0000001 
0000011
0002101
0011202

Now just sum. We get this representation, in uncarried ternary.

0013315

Yes, those are not ternary numbers, but they are almost in a valid base 3 representation. Now all you need to do is to do the carries. Start with the units digit.

5 is larger than 2, so subtract off the number of multiples of 3, and increment the second digit of the result as appropriate.

0013322

The second digit is now a 2, a legal ternary digit, so go on to the third digit. Do that carry too,

0014022

Finally yielding the now completely valid ternary number...

0021022

Were my computations correct? I'll let MATLAB make the final judgement for us:

base2dec('011000101',2)
ans =
   197

base2dec('0021022',3)
ans =
   197

Have I pointed out just how trivial this operation was, that I could do the conversion entirely by hand, going essentially directly from binary to ternary, at least once I had that initial table written down and stored?