| From: xxxxxx@philips.com
 | 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?