RR (14,5): Representing numbers
Note: this post covers only integers. Misnomer, yes, but that's not my problem.
Normally, when we write numbers, we use decimal. That's pretty extensible. When saying it, we either say the decimal version, or in proper words. That's not very extensible, since I've got absolutely no idea how this can be extended arbitrarily. Well, of course, I'm going to focus more on binary-based systems, for sake of (ahem) sanity.
Well, there's the obvious and straightforward binary notation. So I'm going to place another restriction here. The bitstring itself must denote when the bitstring ends. Well, then we have the Fibonacci notation, a mixed-radix system with the Fibonacci numbers (excluding the first 1) as the bases. This uses roughly logφ(n×sqrt(5)) bits. There's another one. First, represent the number in binary, then take the bitstring length, express that in unary, and prefix the (unary) length to the binary number with a 0 in between. This takes 2lb(n)+1 bits, where lb is the binary log. Well, this seems to be worse than the Fibonacci notation.
Oh, but wait! What if we represent that unary number using this format? And so on, ad infinitum? The asymptotic length becomes something like lb*(n)+lb(n)+lb(lb(n))+lb(lb(lb(n)))+…, where lb* is the iterated binary logarithm.
Well, of course these notations are next to useless for computers handling large numbers. Now, let the basic unit be the byte. We may first represent the number in base 256, then prefix it with the length in bytes, stored in one byte. This can only represent numbers up to 256256 = 2211, which is actually plenty enough. But, say, what if we want more? By a similar iterative procedure as outlined above, we can then have 256↑↑…↑↑256 with 257 arrows there, or 256↑2582. Now that's large! But we can do better! Iterating this iterative procedure you'll get to a stage where the chained arrow notation becomes necessary to usefully describe the situation, and iterating this iteration of iteration would allow for arbitrarily large numbers.
Now, how confused are you?
Normally, when we write numbers, we use decimal. That's pretty extensible. When saying it, we either say the decimal version, or in proper words. That's not very extensible, since I've got absolutely no idea how this can be extended arbitrarily. Well, of course, I'm going to focus more on binary-based systems, for sake of (ahem) sanity.
Well, there's the obvious and straightforward binary notation. So I'm going to place another restriction here. The bitstring itself must denote when the bitstring ends. Well, then we have the Fibonacci notation, a mixed-radix system with the Fibonacci numbers (excluding the first 1) as the bases. This uses roughly logφ(n×sqrt(5)) bits. There's another one. First, represent the number in binary, then take the bitstring length, express that in unary, and prefix the (unary) length to the binary number with a 0 in between. This takes 2lb(n)+1 bits, where lb is the binary log. Well, this seems to be worse than the Fibonacci notation.
Oh, but wait! What if we represent that unary number using this format? And so on, ad infinitum? The asymptotic length becomes something like lb*(n)+lb(n)+lb(lb(n))+lb(lb(lb(n)))+…, where lb* is the iterated binary logarithm.
Well, of course these notations are next to useless for computers handling large numbers. Now, let the basic unit be the byte. We may first represent the number in base 256, then prefix it with the length in bytes, stored in one byte. This can only represent numbers up to 256256 = 2211, which is actually plenty enough. But, say, what if we want more? By a similar iterative procedure as outlined above, we can then have 256↑↑…↑↑256 with 257 arrows there, or 256↑2582. Now that's large! But we can do better! Iterating this iterative procedure you'll get to a stage where the chained arrow notation becomes necessary to usefully describe the situation, and iterating this iteration of iteration would allow for arbitrarily large numbers.
Now, how confused are you?
0 Comments:
Post a Comment
<< Home