Compile time square root using C++11 constexpr

constexpr_sqrt.cpp

///
/// @file    constexpr_sqrt.cpp
/// @brief   Calculate integer square roots at compile time using
///          C++11 constexpr.
/// @author  Kim Walisch, <[email protected]>
/// @license Public Domain

#include <iostream>
#include <cassert>
#include <cmath>
#include <limits>
#include <stdint.h>

///////////////////////////////////////////////////////////////////////

#define MID ((lo + hi + 1) / 2)

constexpr uint64_t sqrt_helper(uint64_t x, uint64_t lo, uint64_t hi)
{
  return lo == hi ? lo : ((x / MID < MID)
      ? sqrt_helper(x, lo, MID - 1) : sqrt_helper(x, MID, hi));
}

constexpr uint64_t ct_sqrt(uint64_t x)
{
  return sqrt_helper(x, 0, x / 2 + 1);
}

///////////////////////////////////////////////////////////////////////
/// Testing

#define META_SQRT_TEST(N) \
{ \
  uint64_t square_root = ct_sqrt(N); \
  assert(square_root == (uint64_t) std::sqrt((double) N)); \
  std::cout << "sqrt(" << (uint64_t) N << ") = " << square_root << std::endl; \
}

template <uint64_t N>
struct meta_sqrt_tester
{
  static void test()
  {
    META_SQRT_TEST(N);
    meta_sqrt_tester<N - 1>::test();
  }
};

template <>
struct meta_sqrt_tester<0>
{
  static void test()
  {
    META_SQRT_TEST(0);
  }
};

///////////////////////////////////////////////////////////////////////

int main()
{
  meta_sqrt_tester<100>::test();

  META_SQRT_TEST(std::numeric_limits<int8_t>::max());
  META_SQRT_TEST(std::numeric_limits<uint8_t>::max());
  META_SQRT_TEST(std::numeric_limits<int16_t>::max());
  META_SQRT_TEST(std::numeric_limits<uint16_t>::max());
  META_SQRT_TEST(std::numeric_limits<int32_t>::max());
  META_SQRT_TEST(std::numeric_limits<uint32_t>::max());
  META_SQRT_TEST(std::numeric_limits<int64_t>::max());

  std::cout << "All tests passed successfully!" << std::endl;
  return 0;
}