# 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 <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,

static_assert(
ct::sqrt<ULL, n_max32bit * n_max32bit>::result - 2 == n_max64bit,
}

• If you want larger numbers, you should look at a bignum library, like boost::multiprecision or GMP. Nov 3, 2015 at 15:19

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.

• Sticking constexpr in front of my runtime function does not work. I'm using Visual Studio 2015 (VC++ v140). Nov 3, 2015 at 16:23
• @user2296177 Some day, visual studio will work. Nov 3, 2015 at 16:35