Re: RBB: Really Big Bitvectors

From: Kenneth G. Cavness (
Date: 12/08/95

On Wed, 6 Dec 1995, Mark Coletti wrote:
> 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?

Well, what I was thinking of is that you have some sort of information in 
the 1-3 byte header that could be referenced when trying to distinguish 
whether a particular flag had been set in the actual byte you were 
referencing. For example, to have the "Break into 3 pieces" type 
instruction for the flag "6" being set, and information on how to break 
up that flag, as in "2 1 2" or "4" "3" "1". I'm not really sure how this 
could be viably done, but this is what I had in mind wrt headers.

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

This is, indeed the problem. For many people, memory is not a problem. 
For others, disk space is no problem. For still others, a decrease in 
speed and/or efficency is no object. I happen to fall into the latter. 
Memory and disk space are much mroe precious to me than speed. The 
computer is fast enough for me.

As to elegance, I realise it is not an elegant idea in and of itself, but 
it _does_ give more than 8 flags to a byte, whereas Jaco's bitfield 
scheme basically makes the flags a union, as far as I've seen. (I havne't 
looked at the code yet, but using "affect.bitflags.curse" would seem to 
validate this assumption)

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

The irritant is that I'm almost certain there will _have_ to be more than 
one byte used. However, even if you were to have 55 flags in a 32-bit 
longint, it would be a 23-flag improvement.
Also, the problem of understanding is not really a problem for someone 
used to looking at "C" and is only for my use and those that would "get 
it". I'm not suggesting this as a future revision for circleMUD, but 
rather as a way to perhaps revise CircleMUD or other systems for those 
that wish to use this ssytem.

Kenneth G. Cavness                  |
Associate Editor                    |   "That which is possible is not always
MIDS, TIC                           |    probable." -- Isaac Asimov
1-512-451-7602                      |   "What about the Tuna?" -- Unknown

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