Square root metafunction?

Question

Is it possible to compute the square root of an integer with a metafunction with the following signature :

template<unsigned int N> inline double sqrt();

(or maybe using the constexpr keyword, I don't know what is the best). With that, sqrt<2>() would be replaced by 1.414... at compile-time.

What would be the best implementation for a such function ?

Answer 1

This may not be what you are looking for, but I wanted to make sure you realized that typically with optimization the compiler will calculate the result at compile time anyway. For example, if you have this code:

void g()
{
  f(sqrt(42));
}

With g++ 4.6.3 with optimization -O2, the resulting assembly code is:

   9 0000 83EC1C                subl    $28, %esp
  11 0003 DD050000              fldl    .LC0
  12 0009 DD1C24                fstpl   (%esp)
  13 000c E8FCFFFF              call    _Z1fd
  14 0011 83C41C                addl    $28, %esp
  16 0014 C3                    ret
  73                    .LC0:
  74 0000 6412264A              .long   1244009060
  75 0004 47EC1940              .long   1075440711

The sqrt function is never actually called, and the value is just stored as part of the program.

Therefore to create a function that technically meets your requirements, you simply would need:

template<unsigned int N> inline double meta_sqrt() { return sqrt(N); }

Answer 2

Eigen contains this meta_sqrt which uses binary search:

template<int Y,
         int InfX = 0,
         int SupX = ((Y==1) ? 1 : Y/2),
         bool Done = ((SupX-InfX)<=1 ? true : ((SupX*SupX <= Y) && ((SupX+1)*(SupX+1) > Y))) >
                                // use ?: instead of || just to shut up a stupid gcc 4.3 warning
class meta_sqrt
{
    enum {
  MidX = (InfX+SupX)/2,
  TakeInf = MidX*MidX > Y ? 1 : 0,
  NewInf = int(TakeInf) ? InfX : int(MidX),
  NewSup = int(TakeInf) ? int(MidX) : SupX
};
  public:
    enum { ret = meta_sqrt<Y,NewInf,NewSup>::ret };
};

template<int Y, int InfX, int SupX>
class meta_sqrt<Y, InfX, SupX, true>
{
    public:  enum { ret = (SupX*SupX <= Y) ? SupX : InfX };
};