[futurebasic] A 4 byte solution

Message: < previous - next > : Reply : Subscribe : Cleanse
Home   : November 1998 : Group Archive : Group : All Groups

From: tedd@...
Date: Wed, 11 Nov 1998 17:19:38 -0500
Hi gang:

I just discovered a remarkable way to store a lot of information in a very
small space.

The problem:

Let's say you have a list of things, like days of the month. Where a user
can select any day in any combination. So, how does one record what the
user has selected?

My first attempt was to make an array and fill it with true/false values.
Meaning that if the user picked day 25, then the array(25) = _true. Simple
enough.

However, that required that if I was going to save that information, then I
would have to save the entire array. Like the problem I was presented with
-- which was saving 200 years of dates -- saving a 31 element array for
each month for 200 years gets to be a pretty large file. So, how can one
reduce the problem?

The solution:

Create a byte string. Let each character position mean something, such as:

   DATA "01000000", "02000000", "04000000", "08000000"     '1-4
   DATA "10000000", "20000000", "40000000", "80000000"     '5-8
   DATA "00010000", "00020000", "00040000", "00080000"     '9-12
   DATA "00100000", "00200000", "00400000", "00800000"     '13-16
   DATA "00000100", "00000200", "00000400", "00000800"     '17-20
   DATA "00001000", "00002000", "00004000", "00008000"     '21-24
   DATA "00000001", "00000002", "00000004", "00000008"     '25-28
   DATA "00000010", "00000020", "00000040"                 '29-31


Now, each day has a string associated with it. For example, the 29th day of
the month is "00000010".

As such, if the user only picked the 25th day of the month, then you would
save the string "00000010". From that string, you can tell what the user
selected. That's pretty simple.

But, the beauty of this string algorithm surfaces when the user picks more
than one day. For example. Let's say the user picked the dates of the 6th
through the 12th. That would mean that the days would be:

        20000000  6
        40000000  7
        80000000  8
        00010000  9
        00020000  10
        00040000  11
        00080000  12
        _________
        E00F0000

If one now sums the strings in hex, one finds that the sum "E00F0000" is
another way to record that the user picked the days the 6th through the
12th.

The deconvolving of the string is a matter of simple looking at the sum and
subtracting out the largest members first (i.e., 80000000 is larger than
4000000). What is left over, is then approached in the same manner. You
simply record all the sub-components and that's your data.

This algorithm will work for any combination of 32 items (but, you'll have
to add the 32 element, namely "00000080").

If one wanted to record more than 32 items, then all one would have to do
is to add additional bytes to the string.

I thought that some of you might enjoy my discovery.

If anyone wants a working demo of this, just email me directly.


tedd


___________________________________________________________________
<mailto:tedd@...>	               http://sperling.com/