[boost] Re: Meta-math

From: David M. Jones (djones_at_[hidden])
Date: 2005-01-27 13:57:02

Jason,

I found an algorithm at http://www.pedrofreire.com/sqrt/ that claims to be 
quite fast. I haven't really looked into that. The algorithm needs to be 
modified to always round down (I'm assuming this is what you want, since 
that's what the code you posted does when it works.) Here is the runtime 
version:

unsigned int UIntSqrt(unsigned int n)
{
    unsigned int r;
    for(r = 1; n >= r; n -= r, r += 2);
    return (r - 1) / 2;
}

Putting this into compile-time code is as follows:

template <unsigned int N, unsigned int R = 1, bool C = (N >= R)>
struct Sqrt
{
    static const unsigned int value = Sqrt<(N - R), (R + 2)>::value;
};

template <unsigned int N, unsigned int R>
struct Sqrt<N, R, false>
{
    static const unsigned int value = (R - 1) / 2;
};

I hope this helps,
David

"Jason Hise" <chaos_at_[hidden]> wrote in message 
news:41F884F5.3030508_at_ezequal.com...
>I was just playing around, trying to compute a square root at compile time. 
>I came up with the following:
>
> template < unsigned int N, unsigned int X = 1, unsigned int X2 = ( X + N / 
> X ) / 2 >
> struct Sqrt
> {
>    typedef typename Sqrt < N, X2 > :: ValueHolder ValueHolder;
> };
>
> template < unsigned int N, unsigned int X >
> struct Sqrt < N, X, X >
> {
>    struct ValueHolder
>    {
>        enum ValueStorage
>        {
>            Value = X
>        };
>    };
> };
>
> This works for most values, but unfortunately some ( like 80 ) end up 
> oscillating and X never becomes equal to X2.  How could I go about 
> correcting this?
>
> -Jason
>
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost
>