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

Question

Let these data types be 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 a way to implement the function:

 toBNat :: UNat -> BNat 

What works in O(N) , performing only one pass through UNAT?

Answer 1

To increase the binary digit, you need to flip the first zero at the end of your number and all previous ones. The cost of this operation is proportional to the number 1 at the end of your input (for this, your should represent the number as a list from right to left, for example, a list of [1; 0; 1; 1] codes for 13).

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

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

let it go

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

is the sum of the elements between two degrees 2. You must make sure that s (k + 1) = 2 * s (k) + 1 (with s (0) = 1), noting that

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

obtained by concatenation

  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 the number should be proportional

  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 have taken care to represent your numbers from right to left, then the naive algorithm is linear (note that you can rename and remain linear if you really need your numbers on the contrary).

Answer 2

I like the other answers, but I find their asymptotic analyzes difficult. Therefore, I propose another answer that has a very simple asymptotic analysis. The main 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 repeating divMod .

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

Asymptotic analysis is now quite simple. Given the number n in unary notation, divMod2 takes O (n) time to get a number equal to half — for example, it takes no more than c*n time for sufficiently large n . Thus, iterating this procedure takes a lot of time:

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

As we all know, this series converges to c*(2*n) , therefore toBinary also in O (n) with a constant of evidence 2*c .

Answer 3

If we have a function to increase a BNat , we can do this quite easily by doing UNat , increasing a BNat at each step:

 toBNat :: UNat -> BNat toBNat = toBNat' End where toBNat' :: BNat -> UNat -> BNat toBNat' c Zero = c toBNat' c (Succ n) = toBNat' (increment c) n 

Now this is O(NM) , where M is the worst case for increment . Therefore, if we can do increment in O (1), then the answer is yes.

Here is my attempt to implement increment :

 increment :: BNat -> BNat increment = (reverse End) . inc' . (reverse End) where inc' :: BNat -> BNat inc' End = One End inc' (Zero n) = One n inc' (One n) = Zero (inc' n) reverse :: BNat -> BNat -> BNat reverse c End = c reverse c (One n) = reverse (One c) n 

This implementation is O(N) because you need reverse BNat look at the least significant bits, which gives you O(N) as a whole. If we consider the type of BNat to represent inverse binary numbers, we do not need to drop the BNat , and as @augustss says, we have O (1), which gives you O (N) as a whole.