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

*To*: Common-Lisp@sail.stanford.EDU*Subject*: Logical Operations on Numbers*From*: ELIOT@cs.umass.EDU*Date*: Sun, 22 Jan 89 12:18 EST

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

- Prev by Date:
**New Mail Address** - Next by Date:
**Order of "processing" of arguments** - Previous by thread:
**LOGICAL OPERATIONS ON NUMBERS** - Next by thread:
**argument processing** - Index(es):