(Previous discussion continued)
Re: another operation sebastian.egner@xxxxxx 15 Jan 2005 17:51 UTC

Re: another operation sebastian.egner@xxxxxx 15 Jan 2005 17:51 UTC

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. 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
[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.]

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
make any sense for the purpose of SRFI-60
* 'first-bit-set': from Gambit C.
* 'least-significant-bit-set': verbose name (the operation with not be
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


Dr. Sebastian Egner
Senior Scientist
Philips Research Laboratories
Prof. Holstlaan 4 (postbox WY63, kamer WY 6-55)
5656 AA Eindhoven
The Netherlands
tel:       +31 40 27-42069
fax:      +31 40 27-42566
email: xxxxxx@philips.com