3 ms·
The information theory comment is correct but I’m going to elaborate a little bit with some potentially useful info. For a binary number with N bits, you can r
by tonyarkles 2y ago
The information theory comment is correct but I’m going to elaborate a little bit with some potentially useful info.
For a binary number with N bits, you can represent 2^N values. Easy example: There are 2^8 = 256 possible values that can be represented by an 8-bit value. You can go the other way, too, and ask “how many bits do I need to represent a given value?” by using some math.
2^N = 256
Log2(2^N) = Log2(256)
N = Log2(256) = Log(256)/Log(2) = 8
And you can use this to figure out how many bits you need to represent an arbitrary number: N = Log2(1000) = Log(1000)/Log(2) = 9.966. That makes intuitive sense because a 10-bit number has 1024 values.
To get to the theoretical limit you’re asking about we do the same thing. For an arbitrary number x, how many trits do we need to represent it in trinary and how many bits N do we need to represent it in binary? What is the ratio of trits to bits?
x = 3^M and x = 2^N
Log3(x) = M
Log(x) / Log(3) = M
Log2(x) = N
Log(x) / Log(2) = N
And then we can just take that ratio N/M to figure out how many bits N we need to represent M trits:
R = N/M = Log(x)/Log(2) x Log(3)/Log(x) = Log(3)/Log(2)