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