This page is part of the web mail archives of SRFI 60 from before July 7th, 2015. The new archives for SRFI 60 contain all messages, not just those from before July 7th, 2015.
| 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?