Re: RBB: Really Big Bitvectors

From: Graham Gilmore (
Date: 12/07/95

On Wed, 6 Dec 1995, Mark Coletti wrote:

> > 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?

	I spent some time wondering about this myself..  couldn't come up 
with anything that gave any better results than simple 1-bit bits. :)

> > 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.
> 	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.

	Interesting, yeah, but taking merely the first 32 primes or so 
and multiplying them yields something around 2E50 I think.. much bigger 
than a long int <g>.  And simply adding doesn't work because the sum of 
primes can be a prime number...

> > 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.

	If you look at the set of bits as individual objects and 
calculate the possible # of combinations, you get 2^n for n objects.  
Strangely enough, 2^n is the maximum value of an unsigned bitstring of n 
bits...  Coincidence?  I think not  ;)
	I don't think that there is any way to compact the bits any 
further.  Besides, are you REALLY worried about that extra 4 bytes * 10000 
pc's and mobs?  
	Graham Gilmore

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