11
\$\begingroup\$

This computes the integer square root at compile time for any \$0 \le N \le L\$ where \$L\$ is the largest integral representation of template parameter T.

This was motivated by the fact that many of the algorithms I found were not able to handle large values of \$N\$. I also just wanted to practice template meta-programming.

Important: I cannot simply declare the runtime algorithm as a constexpr function because my compiler does not allow it.

The implementation is based on this runtime algorithm:

template <typename T>
T rt_square_root( T num )
{
    T bit{ static_cast<T>( 1 ) << ( sizeof( T ) * 8 - 2 ) };

    while ( bit > num )
        bit >>= 2;

    T res{ 0 };
    while ( bit )
    {
        T delta{ res + bit };
        if ( num >= delta )
        {
            num -= delta;
            res = ( res >> 1 ) + bit;
        }
        else
        {
            res >>= 1;
        }
        bit >>= 2;
    }
    return res;
}

Source

square_root.h

Template meta-programming based implementation of the algorithm:

#ifndef CR_SQUARE_ROOT_H
#define CR_SQUARE_ROOT_H

namespace ct
{
    template <typename T, typename U>
    bool constexpr greater( T a, U b )
    {
        return b < a;
    }

    template <typename T, T num, T bit, bool condition = true>
    class calc_shifted_bit
    {
    private:
        static T constexpr shifted_bit = bit >> 2;

    public:
        static T constexpr result = calc_shifted_bit<T, num,
            shifted_bit, ct::greater( shifted_bit, num )>::result;
    };

    template <typename T, T num, T bit>
    class calc_shifted_bit<T, num, bit, false>
    {
    public:
        static T constexpr result = bit << sizeof( T ) / 2;
    };

    template <typename T, T num, T res, T bit, typename = void>
    class calc_sqrt
    {
    private:
        static T constexpr delta = res + bit;
        static bool constexpr num_gt_delta = num >= delta;

    public:
        static T constexpr result = calc_sqrt
            <T,
            num_gt_delta ? num - delta : num,
            num_gt_delta ? ( res >> 1 ) + bit : ( res >> 1 ),
            ( bit >> 2 )
            >::result;
    };

    template <typename T, T num, T res, T bit>
    class calc_sqrt<T, num, res, bit, std::enable_if_t<( bit == 0 )>>
    {
    public:
        static T constexpr result = res;
    };

    template <typename T, T n>
    struct sqrt
    {
        static T constexpr result =
            calc_sqrt
            <T, n, 0,
                calc_shifted_bit
                <T, n,
                static_cast<T>( 1 ) << ( sizeof( T ) * 8 - sizeof( T ) / 2 )
                >::result
            >::result;
    };
}

main.cpp

Some tests, compilation time seems fast, but I'm not very experienced with template meta-programming costs:

#include <limits>

int main()
{
    using ULL = unsigned long long;
    using UL  = unsigned long;

    auto constexpr n_max64bit = std::numeric_limits<ULL>::max();
    auto constexpr n_max32bit = std::numeric_limits<UL>::max();

    static_assert(
        ct::sqrt<ULL, n_max64bit>::result == n_max32bit,
        "bad square root" );

    static_assert(
        ct::sqrt<ULL, n_max32bit * n_max32bit>::result - 2 == n_max64bit,
        "bad square root" );
}
\$\endgroup\$
  • \$\begingroup\$ If you want larger numbers, you should look at a bignum library, like boost::multiprecision or GMP. \$\endgroup\$ – AJMansfield Nov 3 '15 at 15:19
2
\$\begingroup\$

Since you're on a C++14 compiler, the simplest solution is just to stick constexpr in front of your runtime algorithm:

template <typename T>
constexpr T rt_square_root(T num)
{
    /* exact same code as before */
}

static_assert( rt_square_root(N_1 * N_1) == N_1, "bad square root" );

I'm not sure there's a compelling reason to do it any other way.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Sticking constexpr in front of my runtime function does not work. I'm using Visual Studio 2015 (VC++ v140). \$\endgroup\$ – user2296177 Nov 3 '15 at 16:23
  • 8
    \$\begingroup\$ @user2296177 Some day, visual studio will work. \$\endgroup\$ – Barry Nov 3 '15 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.