Re: [stella] Thinking like a computer (harder than it sounds)

Subject: Re: [stella] Thinking like a computer (harder than it sounds)
From: slapdash@xxxxxxxxxxxx (Russ Perry Jr)
Date: Mon, 31 May 1999 15:17:49 -0600
"Andrew Davie" <adavie@xxxxxxxxxxxxxxxxx>
>Some time ago, I wrote about fractional bit resolution for storing values.
>This method is rather applicable here, and I'd refer everyone back to my
>earlier posting (about a year ago).  Basically, it is quite possible (and
>extremely efficient memory-wise) to store ranges of values in non-integer
>bit widths.

Andrew is right, but one thing that should be pointed out is that this
memory efficiency can come at the price of execution speed.  I haven't
programmed anything for the 2600 yet myself, but I think I can safely say
that that's the "fun" of programming it -- memory vs speed.  You gotta
be tight on both!

>Storing 52 cards (excluding joker) would require just 5.7005 (approx) bits
>per card, or 296.43 bits (approx) to store an entire deck (randomly, with
>every card uniquely identified).  Each card identified by a unique number.
>That is, each card requires log(2)52 bits of information, and there are 52
>cards.  That's just a tad over 37 bytes (37.052) to store the whole deck.

Of course, Andrew doesn't have a perfect example to counter, as the mild
packing I describe only takes 39 bytes for the deck, not much of a savings
here.  But perhaps it would do good to explain why...

A card requires two bits of information to identify -- suit, and value.
There are four suits, and we can encode them in 2 bits, with NO waste.
There are 13 values, which we can encode in 4 bits, wasting 3 states.
This is a "small" amount of waste (3 of 16); if we had 9 values, we'd
waste 7 states (using 9 of 16).  If our first identifier also had waste,
combining the two would very likely add to our savings...

>Other information can be added (and retrieved) in a similar bit-packing
>fashion.  It does work, though it looks strange.

And implementation time required increases.

>I think I just saved uh.... 15 bits ;)

This is why this particular example isn't a good one to make Andrew's case.
On the other hand, if you look at my UNcompressed scheme below, there are
greater savings yet.  The beauty of it is, with Solitaire we don't really
NEED to worry about savings because with just the simple tricks that Erik
brought up (the ace piles and build piles, up and down cards) save enough
memory that we don't need to do much more, and can save cycles on the
implementation by not having to unpack the card values.

>Russ has a good solution for this particular problem, but fractional bit
>storage is  good for ANY data you want to stor; you are guaranteed NO wasted
>or unused bits, other than the ones not used on the very end of the last
>byte (which, of course, you can use for other purposes).

Absolutely true...  If we had 3 values to store, two with three states each
and one with 7 states, each would require 2 bits, 2 bits and 3 bits
respectively, or 7 bits total.  But there are only 3x3x7 = 63 possible
combinations, which we can store in 6 bits, wasting only 1 state (not 1
state per value).  With 10 items, we've only saved 10 bits with mild
compression, or 20 if we just went with a byte per item.  BUT if we need
to keep 100, the 100 (or 200) bits of savings really starts to add up.

>Retrieval and modification of values is somewhat more difficult, but if
>memory is tight, this is the way to go.

Right, it may in fact be the only solution...  And most packing routines
should be somewhat generalizable and therefore reuseable.

>I'd really advise a close reading of my posting from way-back.

Well, right now, I'd say get coding Solitaire and/or Columns so a) we have
a new game(s) and b) you get some 2600 coding that isn't too complicated,
but then go back and read Andrew's post for your next game, which will
undoubtedly require more memory because it'll be bigger and better. :-)

//*================================================================++
||  Russ Perry Jr   2175 S Tonne Dr #105   Arlington Hts IL 60005  ||
||  847-952-9729    slapdash@xxxxxxxxxxxx    VIDEOGAME COLLECTOR!  ||
++================================================================*//



--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/

Current Thread