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> <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 "where is the manual, again?")</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: +31 40 27-42069<br> fax: +31 40 27-42566<br> email: sebastian.egner@xxxxxxxxxxx</font>