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

conversion between bignums and bitvectors

Long ago I considered the options and chose bignums over bitvectors for
keeping track of bits in my program.  I'm happy with that decision for
lots of reasons, but there are some inner functions where it would be
very beneficial to convert a bignum to a bitvector, do all of the
necessary twiddling, and convert back.  (Cutting down on 50 hour
runtimes for a set of cases.)  Given that I know the maximum size of the
bignum, I wrote the following simple routines to do the conversion:

(defun num->vec (num &optional bitv)
  "copies the number into the bitvector"
  (or bitv (setq bitv (make-array (list (array-dimension *rule-vector* 0))
				  :element-type 'bit)))
  (loop for n from 0 to (- (array-dimension *rule-vector* 0) 1)
	do (setf (aref bitv n)(if (logbitp n num) 1 0)))

(defun vec->num (vec &aux (num 0))
  "optimized bitvector to bignum converter"
  ;; note, for 310 bits this conses <=63 words, a binary tree scheme would cons 45 words
  (loop for word from 0 to (ceiling (- (array-dimension vec 0) 1) 31)
	for acc = 0 for offset = (* 31 word)
	do (loop for pos from 0 to (min 30 (- (array-dimension vec 0) 1 offset))
		 when (= 1 (aref vec (+ offset pos)))
		   do (incf acc (ash 1 pos)))
	   (or (zerop acc)
	       (setq num (if (zerop word) acc
			     (dpb acc (byte 31 offset) num)))))

I can think of some improvements to speed these up somewhat, but I
figured there must be an internal or machine coded routine somewhere
that does the obvious word copies or blts and avoid all of the bit by
bit stuff.  Anyone know of any?
-Bill Long