[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: ELIOT@cs.umass.EDU, common-lisp@sail.stanford.EDU*Subject*: Logical Operations on Numbers*From*: Robert A. Cassels <Cassels@STONY-BROOK.SCRC.Symbolics.COM>*Date*: Thu, 12 Jan 89 16:29 EST*In-reply-to*: <8901122046.AA00579@crash.cs.umass.edu>

Date: Thu, 12 Jan 89 15:31 EST From: ELIOT@cs.umass.EDU Section 12.7 (pp 220-225) describes CL operations for manipulating finite sets using integers. Unfortunately there does not seem to be any predicate to determine if one set is a subset of another using this representation. 'logtest' serves as an intersection test, 'logbitp' serves as a member test but to determine subset relations seems to require computing the set difference (with logandc2) and comparing the result with zero. If the sets are moderately large (say several hundred elements) this involves expensive bignum operations that I would like to avoid. One can imagine a compiler noticing the pattern (LOGTEST .. (LOGNOT ..)) and compiling a call to a special routine which didn't do the explicit LOGNOT computation. I don't know of any compiler which does this, though. I have also thought of using bitvectors, but the operations on bitvectors (p 294) only operate on bitvectors of the same length. For vectors, it's not too hard to imagine that the shorter one should be treated as if it were extended with zeros (presumably at the higher index end). It's a little harder to decide what to do in the multidimensional case. Furthermore, the bitvector functions only include bitwise operations, but no subset test here either. Isn't SUBSET considered an important set manipulation primitive? Chris Eliot University of Massashusetts at Amherst Symbolics Common Lisp defines: SCL:BIT-VECTOR-SUBSET-P - Function (BIT-VECTOR-1 BIT-VECTOR-2 &key (:START1 0) :END1 (:START2 0) :END2) ;; BIT-VECTOR-1 is a subset of BIT-VECTOR-2 SCL:BIT-VECTOR-POSITION - Function (BIT BIT-VECTOR &key (:START 0) :END) ;; equivalent to (POSITION BIT BIT-VECTOR :START START :END END) SCL:BIT-VECTOR-ZERO-P - Function (BIT-VECTOR &key (:START 0) :END) SCL:BIT-VECTOR-EQUAL - Function (BIT-VECTOR-1 BIT-VECTOR-2 &key (:START1 0) :END1 (:START2 0) :END2) ;; equivalent to (EQUAL (SUBSEQ BIT-VECTOR-1 :START START1 :END END1) ;; (SUBSEQ BIT-VECTOR-2 :START START2 :END END2)) SCL:BIT-VECTOR-DISJOINT-P - Function (BIT-VECTOR-1 BIT-VECTOR-2 &key (:START1 0) :END1 (:START2 0) :END2) SCL:BIT-VECTOR-CARDINALITY - Function (BIT-VECTOR &key (:START 0) :END) ;; counts the "1" bits At the present time, -SUBSET-P, -EQUAL, and -DISJOINT-P all return NIL if the vectors have different lengths. A more CL-consistent way of doing cardinality is probably by analogy with the COUNT function: BIT-VECTOR-COUNT - Function (BIT BIT-VECTOR &key (:START 0) :END) ;; equivalent to (COUNT BIT BIT-VECTOR :START START :END END)

**References**:**Logical Operations on Numbers***From:*ELIOT@cs.umass.EDU

- Prev by Date:
**argument processing** - Next by Date:
**cs proposal** - Previous by thread:
**Logical Operations on Numbers** - Next by thread:
**Logical Operations on Numbers** - Index(es):