1
$\begingroup$

The most intuitive method of representing an integer is in unary. For example, 10 can be represented as 0000000000, ----------, etc. This requires O(n) space.

The most common method is slightly more complicated. Several different symbols can be used. For example 100 can be represented as 1100100, 144, 64, 100, etc. This requires O(log n)

My question is, is there a next step to this 'sequence' that would allow us to store an integer in sub-log space? Any physically possible way counts, even if it isn't feasible.

Any proof or disproof would be appreciated, as long as it isn't too complicated.

  • 0
    It would be possible if you would have an infinite alphabet (if you don't have that, can't do better than logarithmic, as pointed out by Andre Nicolas). Is this physically possible? I don't know, but one simple attempt might be using space and positioning (however, maybe there are only finitely many distances between any two things in our universe).2012-03-13

1 Answers 1

1

No, it's not possible, as a simple argument from information theory shows.

Imagine that you want to represent an integer from 0 to 1023 by a sequence of two symbols, 0 and 1. I assert that one sequence must have length at least 10. Why?

Assume the contrary, that each sequence has length $\le 9$. But there are only $2^9 = 512$ unique sequences with at most nine digits. Clearly, you need at least as many sequences as numbers you want to represent.

This argument readily shows that you $Θ(log n)$ symbols to represent a number from $1$ to $n$.

  • 1
    @TannerL.Swett: I can store all$n$bits in `/dev/null` if I'm not required to retrieve them.2012-03-13