Binary to ternary representation conversion
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
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)
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?