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

*To*: sebastian.egner@xxxxxxxxxxx*Subject*: Re: another operation*From*: Aubrey Jaffer <agj@xxxxxxxxxxxx>*Date*: Mon, 17 Jan 2005 23:40:03 -0500 (EST)*Cc*: srfi-60@xxxxxxxxxxxxxxxxx*Delivered-to*: srfi-60@xxxxxxxxxxxxxxxxx*In-reply-to*: <y9lzmza60o2.fsf@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> (sebastian.egner@xxxxxxxxxxx)*References*: <y9lzmza60o2.fsf@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>

| From: sebastian.egner@xxxxxxxxxxx | Date: Sat, 15 Jan 2005 18:51:25 +0100 | | Hello Aubrey, | | Concerning complexity, you are right: Log2-binary-factors needs | time O(n) for an n-bit argument, whether in Scheme or on the bare | metal. Iterating from the LSB, if the density of ones is d, then the probability of k zero LSBs is d^k. The average number of iterations for long numbers would be O(1/log(d)). So it is faster than linear! | Concerning whether this implies that the operation should be | implemented in Scheme you are wrong: The constant buried in the | O(-) is quite perceptible in practice [the machine implementation | reads a word, tests if all bits are zero, and if so proceeds to the | next word; if not it finds the lsb set within the word.] (integer-length (logand n (lognot n))) is linear (in # of bits), so an iterative implementation would be better. | So I am happy you introduced log2-binary-factors, which is exactly | the operation I mentioned. | | With respect to the name: Unfortunately, I do not know a good one | either. Things I came across or played with: | | * 'bset-min': exactly what it means in my 'Bitset' type; clearly | that doesn't make any sense for the purpose of SRFI-60 | | * 'first-bit-set': from Gambit C. I grepped through gambc30 and gambc40b12 without finding first-bit-set. | * 'least-significant-bit-set': verbose name (the operation with not | be used that frequently, so its use is limited by "where is the | manual, again?") | | * 'find-lsb': shorter name, abbreviation 'lsb' might ring some bells | | * 'binary-valuation': the operation finds the number theoretic | valuation of its argument as a 2-ary number; I would advise against | this name, if only because most people have never heard of | valuations before How about COUNT-BINARY-FACTORS?

**Follow-Ups**:**Re: another operation***From:*sebastian . egner

**References**:**Re: another operation***From:*sebastian . egner

- Prev by Date:
**Re: Twos complement assumption, other issues** - Next by Date:
**Re: another operation** - Previous by thread:
**Re: another operation** - Next by thread:
**Re: another operation** - Index(es):