Re: [boost] [math] pow redux and observations

From: John Moeller (fishcorn_at_[hidden])
Date: 2008-05-20 13:06:13

John Moeller <fishcorn <at> gmail.com> writes:

> I noticed that the trunk now has corrections for pow<N> to reduce template 
> instantiations.  However, the "N=1" specialization isn't correct.  The second 
> template parameter (bool odd) should be "true," not "false."  I could be 
> mistaken that 1 is an odd number, though.  
> 
> As it is now, the whole template would work, but would ignore the 1/false 
> specialization and create a new 1/true specialization that just multiplies 
> "base" by the result of 0/false.  Changing 1/false to 1/true will just cause 
> it 
> to return "base," as desired.

One more thing.  Note that this is an honest question from me:

Can it be proportionally difficult for a compiler to inline a series of nested 
function calls the deeper the calls go?

If the answer to this question is "yes," it may be advantageous to alter the 
base template of positive power from this:

template <int N, bool odd>
struct positive_power
{
    template <typename T>
    static typename tools::promote_args<T>::type result(T base)
    {
        return base*positive_power<N-1, (N-1)%2>::result(base);
    }
};

to this:

template <int N, bool odd>
struct positive_power
{
    template <typename T>
    static typename tools::promote_args<T>::type result(T base)
    {
        return base*positive_power<2, false>::result(
                  positive_power<N/2, (N/2)%2>::result(base));
    }
};

The reason is that for pow<31>, the first generates calls that go 8 deep with 3 
2/F calls:

31/T, 30/F, 15/T, 14/F, 7/T, 6/F, 3/F, 2/F

while the second generates calls that go 5 deep with 4 2/F calls:

31/T, 15/T, 7/T, 3/T, 1/T

The second generates one more 2/F call than the first, but the 2/F calls don't 
add to the depth of the call; they're sibling calls to the recursive calls.  
This may only be a minor problem for builtin types, but I could see this being 
a problem for a "mod-multiplication" type, for example, that can raise numbers 
to high powers.