(Previous discussion continued) | ||
Re: another operation | Aubrey Jaffer | 18 Jan 2005 04:40 UTC |
Re: another operation Aubrey Jaffer 18 Jan 2005 04:40 UTC
| 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?