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

Re: another operation



Hello Aubrey,</font>
<br>
<br><font size=2 face="sans-serif">Concerning complexity, you are right:
Log2-binary-factors needs time O(n)</font>
<br><font size=2 face="sans-serif">for an n-bit argument, whether in Scheme
or on the bare metal. Concerning</font>
<br><font size=2 face="sans-serif">whether this implies that the operation
should be implemented in Scheme </font>
<br><font size=2 face="sans-serif">you are wrong: The constant buried in
the O(-) is quite perceptible in practice</font>
<br><font size=2 face="sans-serif">[the machine implementation reads a
word, tests if all bits are zero, and if so</font>
<br><font size=2 face="sans-serif">proceeds to the next word; if not it
finds the lsb set within the word.]</font>
<br>
<br><font size=2 face="sans-serif">So I am happy you introduced </font><font size=2><tt>log2-binary-factors</tt></font><font size=2 face="sans-serif">,
which is exactly</font>
<br><font size=2 face="sans-serif">the operation I mentioned.</font>
<br>
<br><font size=2 face="sans-serif">With respect to the name: Unfortunately,
I do not know a good one either.</font>
<br><font size=2 face="sans-serif">Things I came across or played with:</font>
<br><font size=2 face="sans-serif">* 'bset-min': exactly what it means
in my 'Bitset' type; clearly that doesn't</font>
<br><font size=2 face="sans-serif">make any sense for the purpose of SRFI-60</font>
<br><font size=2 face="sans-serif">* 'first-bit-set': from Gambit C.</font>
<br><font size=2 face="sans-serif">* 'least-significant-bit-set': verbose
name (the operation with not be used</font>
<br><font size=2 face="sans-serif">that frequently, so its use is limited
by &quot;where is the manual, again?&quot;)</font>
<br><font size=2 face="sans-serif">* 'find-lsb': shorter name, abbreviation
'lsb' might ring some bells</font>
<br><font size=2 face="sans-serif">* 'binary-valuation': the operation
finds the number theoretic valuation</font>
<br><font size=2 face="sans-serif">of its argument as a 2-ary number; I
would advise against this name,</font>
<br><font size=2 face="sans-serif">if only because most people have never
heard of valuations before</font>
<br>
<br><font size=2 face="sans-serif">Sebastian.</font>
<br><font size=2 face="sans-serif"><br>
----<br>
Dr. Sebastian Egner<br>
Senior Scientist<br>
Philips Research Laboratories<br>
Prof. Holstlaan 4 (postbox WY63, kamer WY 6-55)<br>
5656 AA Eindhoven<br>
The Netherlands<br>
tel: &nbsp; &nbsp; &nbsp; +31 40 27-42069<br>
fax: &nbsp; &nbsp; &nbsp;+31 40 27-42566<br>
email: sebastian.egner@xxxxxxxxxxx</font>