Logical Operations on Numbers

[ELIOT@cs.umass.EDU]

   From:	IN%"seb1525@draper.COM" 20-JAN-1989 12:12
   Subj:	LOGICAL OPERATIONS ON NUMBERS

   From: SEB1525@mvs.draper.COM
   To: common-lisp@SAIL.STANFORD.EDU


   Isn't SUBSETP of A and B, where A and B are integers, implementable by
    (eql B (logior A B))?

Yes.  It is also (zerop (logandc2 A B)).  However, these expressions
are not efficient.  Suppose that the sets are large, hundreds or thousands
of elements.  In this case A and B are going to be 'bignums', certainly
not FIXNUMS.  Assuming that bignums are implemented so they can be 
operated on as a series of chunks we have:


	A = a1'a2'a3'...'an
	B = b1'b2'b3'...'bn
 

SUBSET implemented directly is:
	(AND[i=1..n] (%subset ai bi))

Where %subset operates on a single chunk.  AND[i=1..n] is a short circuit
logical 'AND' operation.  This requires n operations, and allocates NO new
memory.

SUBSET implemented as (eql B (logior A B)) requires n operations to compute
the logior, perhaps some overhead to normalize the new bignum,
plus n more operations to compute EQL, plus it allocates
memory to store max(A, B).

SUBSET implemented as (zerop (logandc2 A B)) requires n operations
to compute the logandc2, perhaps some overhead to normalize the new bignum,
and 1 operation to compute zero, plust it allocates memory to store
the intermediate result.  This is slightly more efficient, because
ZEROP is microscopically more efficient that EQL.  (ZEROP is FALSE for
all bignums.  EQL has to look at them.)  Furthermore the intermediate
result may be smaller than the intermediate result in the logior
construct.

I draw three conclusions from this.

(1) A naive computation of subset in Common Lisp requires approximately
twice the number of operations than it should, due to missing primitives.

(2) An optimizing compiler should try to recognize the SUBSET operation
and compile it efficiently.  This may be difficult, because there are
at least two (and probably many) ways to encode this operation using the
existing Common Lisp primitives.

(3) For logical completeness, clarity and consistency of source programs
and efficient implementation of some algorithms Common Lisp should be
extended to include a logical subset operation for integers.  The name
subsetp is already used (CLtL P.279) so I propose LOGSUBSETP with
semantics equivalent to:

(defun logsubsetp (a b)
  (zerop (logandc2 a b)))