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 が列挙型を変数に効果的に悪用していることです。問題は、列挙型が内部的に整数として扱われるため、それらから浮動小数点値を取得しようとすることが妨げられることです。ただし、整数部分と指数の 2 つの結果を作成する独自の浮動小数点形式を作成できる場合があります。のように、これをフロートに処理する必要があります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 を計算し、float に格納します。

余分な変換作業は目的に反しますが、指数を 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 に答える