AMDG Paul A. Bristow wrote:

Murilo Adriano wrote:

...

I implemented a function [0] which computes the logarithm in base two of integers and want to know what naming is most appropriated:

ilog2

or simply

log2

My instinct is for log2 so it might be specialised for floating point too.

log2 conflicts with the C++0x library which works with floating point (and returns a double when it's given an integer). Also, does the function compute floor(log2(x)) or ceil(log2(x))? In Christ, Steven Watanabe

...

Also, does the function compute floor(log2(x)) or ceil(log2(x))?

floor(log2(x))

So... how about "most_significant_bit" ? John.

AMDG Murilo Adriano Vasconcelos wrote:

2010/7/15 Steven Watanabe

...

log2 conflicts with the C++0x library which works with floating point (and returns a double when it's given an integer)

This is the point.

You mean you want log2 for integers to return an integer? IMHO, this is wrong. The standard explicitly specifies what should happen if an integer is passed to any of the cmath functions. The standard only specifies that there shall be sufficient extra overloads to accomplish this. If you use log2, it is likely to result in either unexpected results or overload ambiguities, possibly differing between standard library implementations. I think ilog2 is better as it matches the convention used by logb and ilogb. In Christ, Steven Watanabe

From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Murilo Adriano Vasconcelos Sent: Friday, July 16, 2010 1:34 PM To: boost-users@lists.boost.org Subject: Re: [Boost-users] About naming of integer log in base 2 Glancing at your code, I note you don't explicitly check that type T is integer (but perhaps is_signed does that?) But I feel that * If `value` is equal to 0, the value returned is undefined may be evil in some peoples opinion. Of course it is always a vexed question what to do for the corner cases like this. I am sure that this sort of issue will raise its ugly head for other functions. That is because I made count_leading_zeros [1] function to be conditionally compiled: if the compiler is GCC, the functions makes the use of GCC's builtin functions [2] for performance. The function used in count_leading_zeros is __builtin_clz(l and ll) wich is undefined for the value 0. So if the policy requires throwing an exception, then it would mean checking argument is != 0 (but not if the fastest 'ignore errors' policy is chosen). Or return -1 might be another policy. All are potentially reasonable choices. The initial intent was log2(0) = -1, you can check if your compiler isn't GCC that count_leading_zeros(T(0)) is always sizeof(T) * 8 (all bits are leading zeros). But one of the intents of this implementation is performance so, using compiler optimized functions is desired. So the function to be analyzed in this case is count_leading_zeros. I can see the 'need for speed', but that doesn't change the argument for using policies to allow users to control at compile time how exceptional situations are handled. Policies should have no effect on run time, apart from any checks implied by the chosen policy. Paul --- Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com

What if I make 2 versions of ilog2:

- unchecked_ilog2(T value) - don't checks the input value - ilog2(T value) - returns -1 if value == 0 else returns unchecked_ilog2(value)

Following the line of: http://www.boost.org/doc/libs/1_43_0/libs/math/doc/sf_and_dist/html/math_too...

Maybe, it depends on the relative cost of two: the reason for unchecked_factorial is that low-order factorials are often used inside the inner loop of a computation, where anything more expensive than a simple table lookup is out of the question (and the check can easily be moved outside the loop anyway). Does the same thing apply here.... or is the cost of the check trivial compared to the bit manipulations? I don't know the answers to these BTW, just some questions you might want to think about ;-) ilog2 isn't a bad name BTW, John.

From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Murilo Adriano Vasconcelos Sent: Tuesday, July 20, 2010 3:39 PM To: boost-users@lists.boost.org Subject: Re: [Boost-users] About naming of integer log in base 2 Hi, Maybe, it depends on the relative cost of two: the reason for unchecked_factorial is that low-order factorials are often used inside the inner loop of a computation, where anything more expensive than a simple table lookup is out of the question (and the check can easily be moved outside the loop anyway). Does the same thing apply here.... or is the cost of the check trivial compared to the bit manipulations? I don't know the answers to these BTW, just some questions you might want to think about ;-) Thank you John! I thought better and followed Paul's recommendations and implemented math::policies on ilog2() [0], and also changed the count_leading_zeros(T value) to return the size in bits of T when value is equal to 0 (all bits are leading 0's). So I've added two ifs, but think that the design of the functions are better. [0] - https://svn.boost.org/trac/boost/browser/sandbox/SOC/2010/bits_and_ints/boos... Looks more promising, but you have a typo in the error message ;-) retunrning -1", and maybe you need to document some examples of using policies that don't bother to check or at least do so quietly (your original idea), just quietly return -1, produce a message and return -1, or message and then throw an exception? But maybe it's a TODO ;-) Paul --- Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com

From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Murilo Adriano Vasconcelos Sent: Wednesday, July 21, 2010 10:49 PM To: boost-users@lists.boost.org Subject: Re: [Boost-users] About naming of integer log in base 2

and maybe you need to document some examples of using policies that don't bother to check or at least do so quietly (your > original idea), just quietly return -1, produce a message and return -1, or message and then throw an exception.

I should have said that there is an example at \boost_1_43_0\libs\math\example\error_policy_example.cpp and you will also want to provide some Boost.Test style tests too - something like BOOST_CHECK_EQUAL(ilog2(1), 1); // Some plain values... ... BOOST_CHECK_EQUAL(ilog2(FFFFFFFF), 1); // Some cases that might cause trouble. BOOST_CHECK_EQUAL(ilog2(std::numeric_limits::max()), 1); // Other cases that might cause trouble. Cases that really will cause trouble... in this case zero. BOOST_CHECK_EQUAL(ilog2(0), -1); // default policy is to just return -1 (or whatever you decide for default). BOOST_CHECK_THROW(ilog2 > > (0)); // policy that throws an exception for zero. In the math library, these tests are obscured by using macros to repeat them for many functions and policies, but you will find many examples to help you. Setting this up is really mind-numbingly boring but is very well worth it to provide quality assurance for the users - Boost quality. It will make passing a review much more likely. Have fun! Paul --- Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com

From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Murilo Adriano Vasconcelos Sent: Friday, August 13, 2010 1:04 AM To: boost-users@lists.boost.org Subject: Re: [Boost-users] About naming of integer log in base 2 Hi Murilo

and maybe you need to document some examples of using policies that don't bother to check or at least do so quietly

(your > original idea), just quietly return -1, produce a message and return -1, or message and then throw an exception. I should have said that there is an example at \boost_1_43_0\libs\math\example\error_policy_example.cpp and you will also want to provide some Boost.Test style tests too - something like BOOST_CHECK_EQUAL(ilog2(1), 1); // Some plain values... ... BOOST_CHECK_EQUAL(ilog2(FFFFFFFF), 1); // Some cases that might cause trouble. BOOST_CHECK_EQUAL(ilog2(std::numeric_limits::max()), 1); // Other cases that might cause trouble. Cases that really will cause trouble... in this case zero. BOOST_CHECK_EQUAL(ilog2(0), -1); // default policy is to just return -1 (or whatever you decide for default). BOOST_CHECK_THROW(ilog2 > > (0)); // policy that throws an exception for zero. In the math library, these tests are obscured by using macros to repeat them for many functions and policies, but you will find many examples to help you. Setting this up is really mind-numbingly boring but is very well worth it to provide quality assurance for the users - Boost quality. It will make passing a review much more likely. I have added some tests: http://svn.boost.org/svn/boost/sandbox/SOC/2010/bits_and_ints/libs/integer/t... A good start (though I am not clear what using the macro ILOG2_TEST really buys you. It will be less familiar to Boost users. It isn't as if it saves you much typing? I haven't looked at the coverage of difficult cases but it's on the right track. Other tests can be added as you (or worse, other people) find bugs (features) ;-) You might like to indicate what feature is being tested as a comment - unless it's obvious. And examples: http://svn.boost.org/svn/boost/sandbox/SOC/2010/bits_and_ints/libs/integer/e... I'd avoid using BOOST_TEST in examples. The policies example isn't quite the template that users can copy and paste to get them started quickly. (And policies appear to be a bit scary - until you realise that most of time you can just ignore them - until you need a better error message etc. So the example would better show at least two cases - err silently and return -1 or whatever, and err with some informative output. ). (It took a real whizz like John Maddock to devise and apply policies. My contribution was to complain that you couldn't do some things that reasonable users would need to!). I also think it is helpful to include the output from the example as a comment. I think it often fits nicely on the end of the same line as the cout << .... (Saves moving ones eye down to notes at the end (or worse running the example to find out!). Of course if the output is long you will need another line, or it will fit better at the end. That can be found in the docs: http://svn.boost.org/svn/boost/sandbox/SOC/2010/bits_and_ints/libs/integer/d... st_integer.bits_and_ints.integer_logarithm_base_2__ilog2_function__ Looking very smart J Have fun! I am having, thank you :) J Keep up the good work! (I hope some people will start to use this collection 'in anger' soon?) PS I noted typos for 'wich' in more than one place. and legth in Not found a string of consecutive ones with legth at least 20 and lots of "it's" that should be "its" Only use "it's" if short for "it is" !! --- Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com

From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Murilo Adriano Vasconcelos Sent: Sunday, August 15, 2010 5:32 PM To: boost-users@lists.boost.org Subject: Re: [Boost-users] About naming of integer log in base 2 <big snip> That can be found in the docs: http://svn.boost.org/svn/boost/sandbox/SOC/2010/bits_and_ints/libs/integer/d... st_integer.bits_and_ints.integer_logarithm_base_2__ilog2_function__ Looking even smarter J Paul PS The speed of your brain is deceiving your fingers ;-) " retunrning -2" And beware that the way QuickBook works means that there is no protection from running out of the code boxes if line are too long. So, for example, this comment // Error in function boost::ilog2(i): ilog2 is indeterminate for value 0, returning -1 runs over the box (unless you reduce the font size to 2 pixels per char ;-) So it might be better on (or sometimes split onto) the next line?