6

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

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

(或者也许使用 constexpr 关键字,我不知道什么是最好的)。这样,sqrt<2>()1.414...在编译时替换为。

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

4

3 回答 3

8

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

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); }
于 2012-09-02T04:58:50.450 回答
5

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 };
};
于 2015-03-29T16:34:16.907 回答
0

我看到的问题是 metaP 有效地将枚举滥用到变量中。问题是枚举在内部被视为整数,这排除了尝试从中获取浮点值的可能性。但是,您可以创建自己的浮点格式来创建两个结果,一个整数部分和一个指数。您仍然必须将其处理为浮点数,如Out = Sqrt<42>::mantissa * pow(10,Sqrt<42>::exponent);. 实际上确定值留给读者作为练习,但您可能必须向上缩放输入(按 10 的偶数幂),计算根,并存储您之前使用的 -power/2。

要计算 sqrt<42>,您首先将指数枚举设置为合适的幂,例如“-4”(越小,小数越多,但要注意溢出)。然后将输入乘以“10^(-2*exponent)”。在这种情况下,您会得到 42*10^8 = 4200000000。然后,您可以取这个值的根,得到“64807”作为最终值。在运行时,您计算 "val * 10 ^ exponent" = "64807 * 10 ^ -4" = 64807 * 0.0001 = 6.4807m 并将其存储到浮点数中。

额外的转换工作有点违背了目的,但您可以通过将指数存储为 10^k (即 10^4)然后执行out=sqrt<x>::mantissa/sqrt<x>::exponent.

编辑我刚刚注意到,使用尾数/指数方法,指数的选择是任意的,只要它大于最终根的整数部分。它甚至可以是一个常数,这可以简化元函数的设计。例如,在 42 的情况下,您可以选择“指数”始终为 6000。然后将输入乘以 6000^2,取乘积的整数根,然后在运行时将结果除以 6000 得到根. 它没有将输出视为 a*10^b,而是使用关系 sqr(x*b^2)=sqr(x)*b。数学检查:

  • 42*6000*6000=1512000000
  • 平方(1512000000)=38884
  • 38884/6000=6.4806(平方为 41.999)
于 2012-09-02T04:37:09.420 回答