Brian Hurt wrote:
The basic functionality I was thinking of implementing was:
- get, set (to 1), clear (to 0), invert individual bits
- get, set, clear, invert ranges of bits
- bitwise operators- and, or, xor, negation
- shifts (already implemented), rotates.
It is in fact very useful to use GMP integers as sets of naturals (i.e., the set of their positions containing a bit set to one). For this, the following functionality is desirable:
- 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.
You can look at our code for doing that at
http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/~checkout~/ppl/src/SatRow.cc?rev=1...
Cheers
Roberto
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.
http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/~checkout~/ppl/src/SatRow.cc?rev=1...
Is your "next" routine the same as mpz_scan1?
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...
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
Roberto Bagnara bagnara@cs.unipr.it writes:
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.
Might be due to function call overhead. Let us know if there's anything particularly poor coming out in scan1.c.
participants (2)
-
Kevin Ryde -
Roberto Bagnara