Here's an old favourite of mine.
RAM is pretty tight on the 2600, this one could come in handy for those with
really really tight space problems. Its a way of using, say, 2 and a HALF
bits to represent a particular datum. That is, you don't have to use a
whole number of bits.
Consider this: typically you may wish to store some data, and the values
may range from 0 to, say, 11. So, you'd probably want to store that in 4
bits (which can represent 0 to 15), saving yourself those other 4 bits in
the byte for other purposes. Neat enough, but you can do better, and
actually only use 3 and-a-bit bits. No, really... you can!
xxxxBBBB
The above shows a typical way of representing a number up to 12 (from 0 to
11), by using the lower 4 bits of a byte - the bits marked "x" can be used
for some other purpose - there are 4 bits available, allowing, say, a value
of 0 to 15 to be stored.
There's a tricky way to improve this. Think in base 12, not in binary. We
only need ONE base 12 digit to represent a number up to 12. Given any byte
of data, knowing that the low bits hold a base 12 digit... all we need is
the remainder when the whole byte is divided by 12 (assume the entire number
is base12, for now). Its pretty simple - switch to base 10 for a second.
If you want the low digit of any base 10 number, you take the remainder when
divided by 10. That is, n MOD base.
So, we have now extracted the number from 0 to 11 and have a byte left which
doesn't have those bits (and fractional bits) used to store that number
(remember, we divided by 12). This number that's left could ALSO have been
encoded to hold other fractional-bit ranges, also in ANY other base. The
method is exactly the same to extract these bits, using the appropriate
divisor.
Think about it. A byte can hold 256 values. By encoding a base 12 number
in it, we still have (256/12 = 21) other values that we can uniquely
represent. This way we could have encoded in the single byte a value from 0
to 11 and another from 0 to 20.
To do that with "whole" bits, we'd need 4 bits for the 0 to 11 and 5 for the
0 to 20... a total of 9 bits (and in the process "wasting" values from 12 to
15 and from 21 to 31 respectively). So, in this example, we saved a single
bit. Thus, my claim that this method effectively encodes values using
fractional bits.
As I said, this is one of my favourites from long ago.
Enjoy!
A
--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/stella.html
