I think we had a lot of communication problems in this thread. But this post should definitely solve the case :-) First of all, I was not criticizing your algorithm! It's the best one I know of (in terms of maximum number of passes) and extremely simple to understand; also its "runtime version"
if (m /= 2) if (x >> m) return m + log2(x >> m, m); else return log2(x, m); else return 0; is one of the fastest I know, on a variety of implementations. Tests show that its templated incarnation is fast to compile too. Thus, far from me saying that it is not a good strategy to calculate the logarithm (and you will have a confirmation below, because I'm proposing it in place of the current implementation). It just has a peculiarity which can be a (little) problem when you don't have a working <limits> header: i.e. it requires you to know in advance how many bits there are, at most, in your number. As I hinted at, when you have the <limits> header that's no problem at all: you start from m = ( 1 + std::numeric_limits<unsigned long>::digits) / 2; and you have efficient, elegant and perfectly portable code. So far so good. For boost, you know that we don't have always a working <limits> header. Now I proposed a few days ago a simplification of our messed up implementation of boost/detail/limits.hpp based on the idea that numeric_limits::digits is *computable* from the maximum value of the corresponding type; e.g.: 1 + static_log2<UINT_MAX> ::value is the value of digits for unsigned int. Of course in this case log2 must not use in turn numeric_limits :-) Well, on the subject of simple implementations, I also proposed adding some toys like these: template <typename T> struct max_of { /* not defined */ }; template <> struct max_of<unsigned char> { static const int value = UCHAR_MAX; }; template <> struct max_of<unsigned short> { static const int value = SHRT_MAX; }; .... .... with which you can get rid of all the stuff that passes __imin, __imax, etc. through the base class in the implementation of /detail/limits.hpp. Besides helping implementing numeric_limits, these min_of and max_of are also IMHO what should be in the integer library in place of the integer_traits (which derives from numeric_limits for no reason). That said I propose, as a first pass, to replace the current static_log2.hpp with this: ----------- code --------------------- // Boost integer/static_log2.hpp header file -------------------------------// // (C) Copyright Daryle Walker 2001. Permission to copy, use, modify, sell and // distribute this software is granted provided this copyright notice appears // in all copies. This software is provided "as is" without express or // implied warranty, and with no claim as to its suitability for any purpose. // See http://www.boost.org for updates, documentation, and revision history. #ifndef BOOST_INTEGER_STATIC_LOG2_HPP #define BOOST_INTEGER_STATIC_LOG2_HPP #include "boost/config.hpp" // The implementation of log2(x) we use here requires knowing // in advance the number of value bits in typeof(x). This info // is obtainable through std::numeric_limits::digits and the // resulting code is perfectly portable across conforming C++ // implementations. In cases where we don't have a working // <limits> header instead we "compute" the number of value bits // by means of // CHAR_BIT * sizeof(x); // which is ok only if x doesn't have unused bits in its object // representation (which is the case for all non conforming // implementations supported by boost) #ifdef BOOST_NO_LIMITS # include <climits> // for CHAR_BIT #else # include <limits> #endif namespace boost { namespace detail { #ifdef BOOST_NO_LIMITS // this must be changed if the broken C++ implementation (which // doesn't provide a correct <limits> header) has padding bits // on unsigned long static const int width_of_unsigned_long = CHAR_BIT * sizeof(1UL); #else static const int width_of_unsigned_long = std::numeric_limits<unsigned long>::digits; #endif // The algorithm is // // if (m /= 2) // if (x >> m) // return m + log2(x >> m, m); // else // return log2(x, m); // else // return 0; // // with computation of m/2 "anticipated" // respect to template instantiation // template <unsigned long x, int m = (1 + detail::width_of_unsigned_long)/2> struct static_log2_impl { enum { c = (x >> m) > 0 }; // x >= 2**m enum { value = c*m + static_log2_impl< (x >> (c*m)), m/2 >::value }; }; template <> struct static_log2_impl<1,0> { enum { value = 0 }; }; } // namespace detail // static_log2 // template <unsigned long x> struct static_log2 { enum { value = detail::static_log2_impl<x>::value }; }; template <> struct static_log2 <1> { enum { value = 0 }; }; template <> struct static_log2 <0> { }; // log2(0) is undefined } // namespace boost #endif // include guard ---------- end code -------------------------- Here are the results obtained with your shell script on my machine: g++ 2.95 current: real 0m58.069s user 0m33.250s sys 0m20.568s new: real 0m43.960s user 0m18.760s sys 0m20.335s g++ 3.2 current: real 0m53.832s user 0m25.031s sys 0m24.484s new: real 0m39.284s user 0m14.240s sys 0m23.280s What do you think? Genny. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost