Boost logo

Boost :

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
>


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk