Binary to ternary representation conversion

Question

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.

Cardiomegaly

How are you converting to decimal? Why wouldn't that same method work for conversion to ternary? – Norvell

@Stephen: He's looking for a direct conversion, no intermediary conversion to decimal. – Avenue

@Jeff M: Right. He converts from base 2 to base 10 without any intermediary conversions. The same algorithm will allow him to convert from base 2 to base 3 without any intermediate conversions. – Norvell

@Stephen Classic conversion: a*2^0 + b*2^1, etc. So I'll have to implement multiplication in ternary arithmetic. This is what I'd like to avoid, just for fun, to find some tricky and fast way. – Cardiomegaly

@Stephen: Ah I see your point. – Avenue

@Vadim Fedorov: Ah, well, you can do it without needing ternary arithmetic. – Norvell

Answer 1

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)

Lelia

Yep, that's the solution I've been coming to myself, but it's cumbersome. I believe it's possible to manage making it shorter by generating the conversion templates, not specifying all in pattern-matching. – Cardiomegaly

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

Magnificent

In fact I need "by hand" algorithm to be implemented in program 'cause data used in computation is data structure having 0/1 states for numerals, not some integer. – Cardiomegaly

After thinking about this, there is always an implicit conversion to decimal. In every step, the decimal representation is always considered. 100 binary (4 in decimal) divided by 11 (3). It's still being converted. – Avenue

@Vadim You are almost certainly better off converting your data structures into numbers and using the computer arithmetic. – Magnificent

@Jeff M: there is no implicit conversion to decimal. division is the same in any base -- it's defined on integers themselves, not on their representations in any specific base. – Norvell

Answer 3

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?

Qumran

I'll note that this approach works for essentially a direct conversion between any two number bases, as long as you compute the appropriate table first. So if you wish to convert from base 3 to base 7, and do it more than once, you can do it efficiently. – Qumran

Answer 4

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 ax^2 + bx + 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)

Delaminate

Answer 5

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.

Norvell

Please see update to the question, I clarified what it is about. – Cardiomegaly

Answer 6

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 convert from base 60 to base 10

Serotonin

"The solution I've already implemented is to convert a number to decimal first." - it was mistake, just converting mentioned algebraic type (BNumber) to Integer. – Cardiomegaly

Answer 7

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.

Vlissingen

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.

Remscheid

Looks like @woodchips was able to do what you said can't be done. – Vlissingen

He's not loading into integers but he's still loading into a non-binary, non-ternary representation for translation purposes. It's a clever solution but it's still an intermediary language, so I don't see that it's significantly different. e.g. how do you resolve 01 + 01 + 01 = 03 in binary or ternary? You can't. – Remscheid

Answer 9

If you use binary-coded-ternary (one pair of bits per trit) you can convert using parallel arithmetic. See this tutorial.

Idleman