Compile time integer square root for large numbers

Question

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" );
}

Answer 1

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.