[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: another operation
| 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
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
| * '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?