[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: another operation

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.

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: sebastian.egner@xxxxxxxxxxx