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

*To*: slug@ai.sri.com*Subject*: conversion between bignums and bitvectors*From*: WJL@ZERMATT.lcs.mit.edu (Bill Long)*Date*: Mon, 17 Dec 1990 07:57:00 -0500

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

- Prev by Date:
**Can I use a Laserwriter with Symbolics system?...** - Next by Date:
**Can I use a Laserwriter with Symbolics system?...** - Previous by thread:
**Mail to CompuServe or Prodegy** - Next by thread:
**Internet/COmpuserve** - Index(es):