平方根函数？

Question

是否可以使用具有以下签名的元函数计算整数的平方根:

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

(或者可能使用constexpr关键字,我不知道什么是最好的).有了它,sqrt<2>()将1.414...在编译时替换.

什么是这种功能的最佳实现？

Answer 1

这可能不是你想要的,但我想确保你意识到通常通过优化,编译器无论如何都会在编译时计算结果.例如,如果您有此代码:

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

使用带有优化-O2的g ++ 4.6.3,生成的汇编代码为:

   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

实际上从未调用sqrt函数,并且该值仅作为程序的一部分存储.

因此,要创建一个技术上符合您要求的功能,您只需要:

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

Answer 2

Eigen包含meta_sqrt使用二进制搜索的:

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