Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

According to a book I am reading, the unary representation of a number exponentially larger than a base k representation of it. I, however, feel that the unary representation should scale linearly with the input.

After all, 1 is 1, 2 is 11, 3 is 111, and so on, right? Wouldn't that be linear?

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

The base $k$ representation of the number $n$ takes $\log_{k}n$ bits, whereas the unary representation takes $n$, and of course $n = k^{\log_{k}n}$

The gap is more apparent with larger numbers, if we take our normal base 10 system, then writing 1000 takes 4 decimal digits, but writing it in unary takes 1000 ones.

share|improve this answer
    
Thanks! I wonder how to prove though that the base $k$ representation of the number $n$ takes $\log_{k}n$ bits... the example with large numbers in base 10 does make sense though. –  John Hoffman Dec 1 '12 at 1:11
2  
A sketch of why it takes a logarithmic amount of space is to get the first digit, you divide your number by your base $k$, the remainder gives you your least significant digit, then you divide the quotient by $k$ again, getting the next digit as the remainder, and so on. So the length of the number $n$ representation base $k$ is the number of times you can divide $n$ by $k$ and get a non-zero quotient. I'll stick an example in the next comment. –  Luke Mathieson Dec 1 '12 at 1:29
2  
Say we have 25, and we want it in base 2. We divide by 2, and get quotient 12, remainder 1, so our base 2 number has 1 as its first bit. Then divide 12 by 2, get quotient 6, remainder 0, so our number-in-progress is 01. Compressing the notation a little now; 6/2 = 3r0 -> 001 : 3/2 = 1r1 -> 1001 : 1/2 = 0r1 -> 11001. At this point our quotient is down to zero, so we're done. This took 5 steps, which is $\lceil \log_{2}25\rceil$ (we need the ceiling function as we can't have a fraction of a digit - there's some other small technicalities too, exact powers take $1+log_{k}n$ digits). –  Luke Mathieson Dec 1 '12 at 1:37
    
Thank you, that makes sense! –  John Hoffman Dec 1 '12 at 1:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.