Re: RBB: Really Big Bitvectors

From: Mark Coletti (
Date: 12/06/95

Kenneth G. Cavness pounded furiously on the keyboard:

> 1. Have a 1-3 byte header that somehow denotes what number is what. Even
> if you have a 32-bit RBB structure with 126-256+ "bits", it's better than
> the original 32-bits you would get otherwise.

	This doesn't scan.  Can you elaborate?

> 2. Have the RBB use only prime numbers. There is an easy algorithm to 
> determine a number's prime eligibility and I'm not sure, but I think there
> are more than the usual for each byte, and especially as you get higher
> up into the numbers.

	This is a kewl idea: using Godel numbers for flags!  
	There are 55 primes between 1 and 255.  (Someone probably
should independantly verify this value.)  This would yield a 6:1
increase in the number of flags in a single byte.  The number of
primes between 1 and 65535 would definitely be way bigger than the
sixteen flags that a two byte integer would normally provide.
	This is a mathematically elegant idea, but I wouldn't use it
because it's not as satisfactory as Jaco's bitfield scheme.  Bitfield
lookups and assignments would be constant time, whereas the Godel
number scheme would be O(n).  (I, erm, _think_.  Anyhoo, this is a
best guess upper bound.)  Worse yet, any implementations couldn't
possibly be as straightforward as ones using bitfields.
	Oh, there's another problem that makes this scheme
intractible: you would have to _multiply_ various primes to yield a
single "compressed" value.  It's safe to say that it wouldn't take
much to overflow a single byte.
	Still an interesting idea.

> 3. Have the RBB use each "bit" in multiples of some number that will allow
> you to use the numbers BETWEEN each "bit" as a pointer that this "bit" has
> been set. Would require a very elaborate algorithm.

	Eeek!  Yesh.  Again, for the sake of understandability,
bitfields are still better.

Mark Coletti                       |  DBA Systems, Inc.  Fairfax, VA                 |  United States Geological Survey  |  Office of Standards & Technology
	 A day without fusion is like a day without sunshine.

This archive was generated by hypermail 2b30 : 12/07/00 PST