c++ - 符号付き Char ATAN2 および ATAN 近似

Question

基本的に、私は 2 つの近似関数を作成しようとしています。どちらの場合も、「x」コンポーネントと「y」コンポーネントを入力し (これらの厄介な n/0 および 0/0 条件に対処するため)、Signed Char 出力を取得する必要があります。ATAN2 の場合、+/-PI の範囲を提供する必要があり、ATAN の場合、範囲は +/-PI/2 である必要があります。

私は昨日ずっと頭を包み込もうとして過ごしました。近似に基づいて全体的に適切なアルゴリズムを見つけるために Excel で遊んだ後:

    X * (PI/4 + 0.273 * (1 - |X|)) * 128/PI // Scale factor at end to switch to char format

次のコードを思いつきました：

signed char nabsSC(signed char x)
{
    if(x > 0)
        return -x;
    return x;
}

signed char signSC(signed char input, signed char ifZero = 0, signed char scaleFactor = 1)
{
    if(input > 0)
    {return scaleFactor;}

    else if(input < 0)
    {return -scaleFactor;}

    else
    {return ifZero;}
}

signed char divisionSC(signed char numerator, signed char denominator)
{
    if(denominator == 0)                // Error Condition
    {return 0;}
    else
    {return numerator/denominator;}
}

//#######################################################################################

signed char atan2SC(signed char y, signed char x)
{
    // @todo make clearer : the code was deduced through trial and error in excel with brute force... not the best reasoning in the world but hey ho
    if((x == y) && (x == 0))                            // Error Condition
    {return 0;}

                                    // Prepare for algorithm Choice
    const signed char X = abs(x);
    signed char Y = abs(y);
    if(Y > 2)
    {Y = (Y << 1) + 4;}

    const signed char alpha1 = 43;
    const signed char alpha2 = 11;
                                    // Make Choice
    if(X <= Y)                          // x/y Path
    {
        const signed char beta = 64;
        const signed char a = divisionSC(x,y);          // x/y
        const signed char A = nabsSC(a);                // -|x/y|

        const signed char temp = a * (alpha1 + alpha2 * A);     // (x/y) * (32 + ((0.273 * 128) / PI) * (1 - |x/y|)))
                                                        // Small angle approximation of ARCTAN(X)
        if(y < 0)                   // Determine Quadrant
        {return -(temp + beta);}
        else
        {return -(temp - beta);}
    }
    else                                // y/x Path
    {
        const signed char a = divisionSC(y,x);          // y/x
        const signed char A = nabsSC(a);                // -|y/x|

        const signed char temp = a * (alpha1 + alpha2 * A);     // (y/x) * (32 + ((0.273 * 128) / PI) * (1 - |y/x|)))
                                                        // Small angle approximation of ARCTAN(X)

        if(x < 0)                   // Determine Quadrant
        {
            Y = signSC(y, -127, 127);                       // Sign(y)*127, if undefined: use -127
            return temp + Y;
        }
        else
        {return temp;}
    }
}

私の絶望的なことに、実装には 180 度もの誤差があり、その間のほぼすべての場所にも誤差があります。(signed char 形式に変換した後、ライブラリの ATAN2F と比較しました。)

私はこのウェブサイトから一般的な要点を得ました: http://geekshavefeelings.com/posts/fixed-point-atan2

どこが間違っているのか誰か教えてもらえますか? そして、この狂気のない ATAN バリアント (範囲の半分以上を見ているため、より正確なはずです) にどのようにアプローチする必要がありますか。

現在、WindowsでQTクリエーター4.8.1を使用しています。この特定のコードのエンドプラットフォームは、最終的には FPU のないマイクロコントローラーになり、ATAN 機能は使用される主要な機能の 1 つになります。そのため、妥当な誤差 (ATAN2 で +/-2 度、ATAN で +/-1 度。これらは現時点では推測であるため、範囲を広げる可能性がありますが、90 度は絶対に受け入れられません!) を伴う効率が目標です。ゲームの。

事前にすべての助けに感謝します!

編集: 明確にするために、ATAN2 と ATAN の出力は符号付きの char 値に出力されますが、2 つの型の範囲は異なる範囲です。

ATAN2 の範囲は -128 (-PI) から 127 (+PI - PI/128) です。

ATAN の範囲は -128 (-PI/2) から 127 (+PI/2 - PI/256) です。

そのため、2 つの出力値は 2 つの異なるデータ型と見なすことができます。

混乱して申し訳ありません。

EDIT2: 暗黙的な int 数値を明示的に signed char 定数に変換しました。

score 0 · Accepted Answer

概要は次のとおりです。以下は追加情報です。

結果の角度 (バイナリ角度測定)は、正確に数学的に単位円を 8 つのくさびに分割します。-128 から 127charを仮定するとatan2SC()、各八分円の結果は 33 個の整数 (0 から 32 + オフセット) になります。(丸めのため、0 から 31 ではなく 0 から 32 です。) の場合atan2SC()、結果は 0 から 64 です。そのため、x,y入力と 0 から 64 の結果を持つ 1 つのプライマリオクタントの結果を計算することに集中してください。両方ともこのヘルパー関数を使用できatan2SC()ます。の場合、中間角を求めるには、を使用します。には、を使用します。atan2SC()at2()atan2SC()aa = at2(x,y)/2atanSC()a = at2(-128, y)
で整数商を見つけると、除算でa = divisionSC(x,y)あまりにa * (43 + 11 * A)も多くの情報が失われます。x,y形式で多分を使用する方程式で atan2 近似を見つける必要がありますat2 = (a*y*y + b*y)/(c*x*x + d*x)。
のように負の絶対値を使用するとよいでしょうnabsSC()。整数の負の範囲は正の範囲以上です。例: -128 から -1 対 1 から 127。を呼び出すときは、負の数と 0 を使用しat2()ます。

[編集]

以下は、簡略化されたオクタント選択アルゴリズムを使用したコードです。これは、 2 の補数を仮定して、の否定が確実x,yに範囲になるように慎重に作成されます。SCHAR_MIN,SCHAR_MAXすべてのオクタントはを呼び出し、iat2()ここで精度を向上させるために改善を行うことができます。注:この時点では 0 ではないため、iat2()除算は行われません。丸めモードと、このヘルパー関数が共有されているかどうかによって、その詳細が決まります。2 ピースごとの線形テーブルが広い整数演算を使用できないことを提案します。それ以外の場合は aa linearです。私はこれでもっと遊ぶかもしれません。x==0xatanSC()(ay+b)/(cx+d)
精度とパフォーマンスの重みは、OP のコードにとって重要なものですが、最適な答えを導き出すのに十分ではありません。iat2()そこで、 OPの詳細の精度を評価するテストドライバーを以下に投稿しました。
3つの落とし穴があります。1) 答えが +180 度の場合、OP は -128 BAM を求めているようです。しかしatan2(-1, 0.0)、+pi が思いつきます。この符号反転が問題になる場合があります。注: atan2(-1, -0.0)--> -pi. 参考文献 2) 回答が +180 度よりわずかに小さい場合、iat2()詳細によっては、整数の BAM 結果が +128 になり、-128 にラップする傾向があります。結果は、atan2()+pi または +128 BAM よりわずかに小さくなります。このエッジ条件は、OP の最終コードで確認する必要があります。3) (x=0,y=0) の場合は、特別な処理が必要です。オクタント選択コードがそれを見つけます。
a のコードは、signed char atanSC(signed char x)高速にする必要がある場合、いくつかif()のと 64 バイトのルックアップテーブルを使用できます。(8 ビットの符号付き char を想定)。この同じテーブルをで使用できますiat2()。

.

#include <stdio.h>
#include <stdlib.h>

// -x > -y >= 0, so divide by 0 not possible
static signed char iat2(signed char y, signed char x) {
  // printf("x=%4d y=%4d\n", x, y); fflush(stdout);
  return ((y*32+(x/2))/x)*2;  // 3.39 mxdiff
  // return ((y*64+(x/2))/x);    // 3.65 mxdiff
  // return (y*64)/x;            // 3.88 mxdiff
}

signed char iatan2sc(signed char y, signed char x) {
  // determine octant
  if (y >= 0) { // oct 0,1,2,3
    if (x >= 0) { // oct 0,1
      if (x > y) {
        return iat2(-y, -x)/2 + 0*32;
      } else {
        if (y == 0) return 0; // (x=0,y=0)
        return -iat2(-x, -y)/2 + 2*32;
      }
    } else { // oct 2,3
      // if (-x <= y) {
      if (x >= -y) {
        return iat2(x, -y)/2 + 2*32;
      } else {
        return -iat2(-y, x)/2 + 4*32;
      }
    }
  } else { // oct 4,5,6,7
    if (x < 0) { // oct 4,5
      // if (-x > -y) {
      if (x < y) {
        return iat2(y, x)/2 + -4*32;
      } else {
        return -iat2(x, y)/2 + -2*32;
      }
    } else { // oct 6,7
      // if (x <= -y) {
      if (-x >= y) {
        return iat2(-x, y)/2 + -2*32;
      } else {
        return -iat2(y, -x)/2 + -0*32;
      }
    }
  }
}

#include <math.h>

static void test_iatan2sc(signed char y, signed char x) {
  static int mn=INT_MAX;
  static int mx=INT_MIN;
  static double mxdiff = 0;

  signed char i = iatan2sc(y,x);
  static const double Pi = 3.1415926535897932384626433832795;
  double a = atan2(y ? y : -0.0, x) * 256/(2*Pi);

  if (i < mn) {
    mn = i;
    printf ("x=%4d,y=%4d  --> %4d   %f, mn %d mx %d mxdiff %f\n", 
        x,y,i,a,mn,mx,mxdiff);
  }
  if (i > mx) {
    mx = i;
    printf ("x=%4d,y=%4d  --> %4d   %f, mn %d mx %d mxdiff %f\n", 
        x,y,i,a,mn,mx,mxdiff);
  }

  double diff = fabs(i - a);
  if (diff > 128) diff = fabs(diff - 256);

  if (diff > mxdiff) {
    mxdiff = diff;
    printf ("x=%4d,y=%4d  --> %4d   %f, mn %d mx %d mxdiff %f\n", 
        x,y,i,a,mn,mx,mxdiff);
  }
}


int main(void) {
  int x,y;
  int n = 127;
  for (y = -n-1; y <= n; y++) {
    for (x = -n-1; x <= n; x++) {
      test_iatan2sc(y,x);
    }
  }
  puts("Done");
  return 0;
}

ところで: 楽しい問題です。

c++ - 符号付き Char ATAN2 および ATAN 近似

1 に答える 1

Related

Reference