[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,</font>
<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><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><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><font size=2 face="sans-serif">Sebastian.</font>
<br><font size=2 face="sans-serif"><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>