[boost] Re: A question about static_log2

From: Gennaro Prota (gennaro_prota_at_[hidden])
Date: 2003-01-22 12:31:36

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.