Is there any efficient way to convert an unary number to a binary number?

Question

Let those datatypes represent unary and binary natural numbers, respectively:

data UNat = Succ UNat | Zero
data BNat = One BNat | Zero BNat | End

u0 = Zero
u1 = Succ Zero
u2 = Succ (Succ Zero)
u3 = Succ (Succ (Succ Zero))
u4 = Succ (Succ (Succ (Succ Zero)))

b0 = End                   //   0
b1 = One End               //   1
b2 = One (Zero End)        //  10
b3 = One (One End)         //  11
b4 = One (Zero (Zero End)) // 100

(Alternatively, one could use `Zero End` as b1, `One End` as b2, `Zero (Zero End)` as b3...)

My question is: is there any way to implement the function:

toBNat :: UNat -> BNat

That works in O(N), doing only one pass through UNat?

Answer 1

I like the other answers, but I find their asymptotic analyses complicated. I therefore propose another answer that has a very simple asymptotic analysis. The basic idea is to implement divMod 2 for unary numbers. Thus:

data UNat = Succ UNat | Zero
data Bit = I | O

divMod2 :: UNat -> (UNat, Bit)
divMod2 Zero = (Zero, O)
divMod2 (Succ Zero) = (Zero, I)
divMod2 (Succ (Succ n)) = case divMod2 n of
    ~(div, mod) -> (Succ div, mod)

Now we can convert to binary by iterating divMod.

toBinary :: UNat -> [Bit]
toBinary Zero = []
toBinary n = case divMod2 n of
    ~(div, mod) -> mod : toBinary div

The asymptotic analysis is now pretty simple. Given a number n in unary notation, divMod2 takes O(n) time to produce a number half as big -- say, it takes at most c*n time for large enough n. Iterating this procedure therefore takes this much time:

c*(n + n/2 + n/4 + n/8 + ...)

As we all know, this series converges to c*(2*n), so toBinary is also in O(n) with witness constant 2*c.

Answer 2

To increment a binary digit, you have to flip the first zero at the end of your number and all the ones preceding it. The cost of this operation is proportional to the number of 1 at the end of your input (for this your should represent number as right-to-left list, eg. the list [1;0;1;1] codes for 13).

Let a(n) be the number of 1 at the end of n:

a(n) = 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ...

and let

s(k) = a(2^k) + a(2^k+1) + ... + a(2^(k+1)-1) 

be the sum of elements between two powers of 2. You should be able to convince yourself that s(k+1)=2*s(k) + 1 (with s(0) = 1) by noticing that

    a(2^(k+1)) ..., a(2^(k+2) - 1) 

is obtained by concatenating

    a(2^k) + 1, ..., a(2^(k+1) - 1) and   a(2^k), ..., a(2^(k+1) - 1)

And therefore, as a geometric series, s(k) = 2^k - 1.

Now the cost of incrementing N times a number should be proportional to

    a(0) + a(1) + ... + a(N)
  = s(0) + s(1) + s(2)  + ... + s(log(N)) 
  = 2^0 - 1 + 2^1 -1 + 2^2-1 + ... + 2^log(N) - 1
  = 2^0 + 2^1 + 2^2 + ... + 2^log(N) - log(N) - 1
  = 2^(log(N) + 1) - 1 - log(N) - 1 = 2N - log(N) - 2

Therefore, if you take care of representing your numbers from right-to-left, then the naive algorithm is linear (note that you can perform to list reversal and stay linear if you really need your numbers the other way around).