[PPL-devel] Re: Integers as bit arrays

[Roberto Bagnara]

Kevin Ryde wrote:
> Roberto Bagnara <bagnara@cs.unipr.it> writes:
> 
>>- searching 0 or 1 bits scanning towards less significant bits;
>>- efficiently deciding whether a set of naturals is a (proper
>>   or non proper) subset of another.
> 
> 
> They're in the tasks list.  If Torbjorn likes the concepts then
> they're only waiting for nice names and good implementations.

Good.  For the names, I think the choice belongs to senior GMP
developer; for the good implementations, what I contributed is
a possible starting point that Brian can refine at will (I will
release it under a different license if that helps).

>>   http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/~checkout~/ppl/src/SatRow.cc?rev=1.20&content-type=text/plain&cvsroot=ppl
> 
> 
> Is your "next" routine the same as mpz_scan1?

More or less.  In particular, our next() routine
can be implemented as

   unsigned long r = mpz_scan1(vec, ++position);
   return (r == ULONG_MAX) ? -1 : r;

However, last time I checked this was significantly slower.
I will re-check though.
Cheers

     Roberto

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara@cs.unipr.it