Re: [boost] A question about static_log2

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2003-01-21 15:41:48

Gennaro Prota:
>[...] in many cases boost has implementations enormously more
>complicated than necessary.

I would recommend that you seriously show how to make simpler 
implementations. I'm sure that significant simplifications, that work as 
well as the more complicated implementation, would be accepted, if you are 
willing to provide enough of the simpler implementation. I'm also positive 
that you would be acknowledged for such work.

>To me instead simplicity is important as much as other aspects,
>and should be abandoned _only_ when it comes, for instance, at
>correctness' or completeness' cost.

Striking a good balance is very difficult. I would recommend that you 
seriously propose alternatives. I'm sure such proposals will be considered.

>I think you are missing something here, maybe the important fact that
>an integer type (unsigned long included) may have padding bits or the
>rules about shift operators.

Not that I know of. I've known the basic definitions concerning shift 
operators and unsigned integral types for a long time.

The point was that the algorithm core does significantly fewer recursions. 
Sure, you can get bogged down in the details of the C++ language, if you 
want to. I was aware of the fact that the technique I used for calculating 
the initial shift count was not perfect when I sent my initial reply. The 
specifics of calculating the proper initial shift count is a minor detail of 
the overall algorithm.

>Proof please?[...]

Please reread the paragraph of my previous post that starts with: "In this 
case it is not necessary to know the exact number of value bits." If the 
initial shift count is chosen correctly, which can always be done, the 
recursion always terminates with the case log2<1,0>.

>[...]adding specializations at "regular intervals", i.e.
>
>template <> struct log2<16>  ..
>template <> struct log2<256> ...
>template <> struct log2<4096> ...
>
>In both cases the timings were practically the same[...]

Are those specialization for the naïve algorithm?

In that case it is not very surprising that they do not significantly 
improve the efficiency of the algorithm. In order for such a set of 
specialization to be effective, you would need quite a few of them. For 
instance, to reduce the maximum time to half on 32-bit unsigned longs, you 
would need something like 2^15 or 2^16 specializations, which is not very 
practical.

Regards,
  Vesa Karvonen

_________________________________________________________________
STOP MORE SPAM with the new MSN 8 and get 2 months FREE* 
http://join.msn.com/?page=features/junkmail