Monday, November 30, 2009

C++: compile time square root (sqrt) using templates

This code computes square root in compile time using C++ templates and binary search:

#include <iostream>
using namespace std;

#define MID(a, b) ((a+b)/2)
#define POW(a) (a*a)

template<int res, int l = 1, int r = res>
class SQRT;

template<int res, int r>
class SQRT<res, r, r> {
   static const int value = r;

template <int res, int l, int r>
class SQRT {
   static const int value = SQRT<res, (POW(MID(r, l)) >= res ? l : MID(r, l)+1), (POW(MID(r, l)) >= res ? MID(r, l) : r)>::value;

int main() {
  cout << SQRT<256>::value << endl;
  return 0;

See codepad paste for more information.

Thanks HELLER[i] for idea.


  1. Interesting. I guess your method instantiates less templates than the one in C++ Templates [1] because it is not using the IfThenElse template. Have you compared the performance? However, I'm sure you could improve it by storing the results rather than recalculating them? I.e.:

    class SQRT {
    static const int mid = MID(r, l);
    static const bool gr = POW(mid) >= res;
    static const int value = SQRT::value;



  2. And another thing for the record since I'm here! Rather than asking "is mid * mid >= res?", I use "is mid >= res / mid?" Why? To avoid integer overflow from mid * mid.