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