Compile time integer square root for large numbers 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 &lt;typename T&gt;
T rt_square_root( T num )
{
    T bit{ static_cast&lt;T&gt;( 1 ) &lt;&lt; ( sizeof( T ) * 8 - 2 ) };

    while ( bit &gt; num )
        bit &gt;&gt;= 2;

    T res{ 0 };
    while ( bit )
    {
        T delta{ res + bit };
        if ( num &gt;= delta )
        {
            num -= delta;
            res = ( res &gt;&gt; 1 ) + bit;
        }
        else
        {
            res &gt;&gt;= 1;
        }
        bit &gt;&gt;= 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 &lt;typename T, typename U&gt;
    bool constexpr greater( T a, U b )
    {
        return b &lt; a;
    }

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

    public:
        static T constexpr result = calc_shifted_bit&lt;T, num,
            shifted_bit, ct::greater( shifted_bit, num )&gt;::result;
    };

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

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

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

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

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


main.cpp

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

#include &lt;limits&gt;

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

    auto constexpr n_max64bit = std::numeric_limits&lt;ULL&gt;::max();
    auto constexpr n_max32bit = std::numeric_limits&lt;UL&gt;::max();

    static_assert(
        ct::sqrt&lt;ULL, n_max64bit&gt;::result == n_max32bit,
        "bad square root" );

    static_assert(
        ct::sqrt&lt;ULL, n_max32bit * n_max32bit&gt;::result - 2 == n_max64bit,
        "bad square root" );
}
Since you're on a C++14 compiler, the simplest solution is just to stick constexpr in front of your runtime algorithm:

template &lt;typename T&gt;
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.