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

• AJMansfield: If you want larger numbers, you should look at a bignum library, like boost::multiprecision or GMP.

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.

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