2

4.12固定小数点の角度の正弦を計算する（できれば高速な）方法を知っている人はいますか？（結果は円の32768分の1または度のいずれかです）

4.12固定小数点は、数値が16ビットで、左に12シフトされることを意味します。したがって、1.0は（1 << 12）または4096になります。0.5は（0.5 << 12）==2048などになります。

4

2 に答える 2

8

最高速度が必要な場合は、事前計算が最適です。2つの16（65,536）の可能な入力があるので、単純なアプローチは、その数の16ビット値の配列を持つことです（合計128Kのメモリが使用されます）。

ただし、メモリをすべて使用したくない場合は、少しだけ改善できます（速度は少し犠牲になります）。

入力がラジアンであると仮定すると（4.12の数値の範囲は0から15.999 ...であり、円のすべての度を表すには不十分であるためです）、次の事実を利用できます。

  • sin (n) = sin (n % (2*PI)) for n >= 2*PI
  • sin (n) = -sin (n - PI) for PI <= n < 2*PI
  • sin (n) = sin (PI - n) for PI/2 <= n < PI

したがって、ルックアップテーブルは0〜PI / 2ラジアンの値のみを保持する必要があり、ストレージ要件を大幅に削減します。0〜15.999の全範囲ではなく、0〜PI / 2（〜1.571）のみを保存します。約90％の削減。

次に、モジュロ（最初のルール）を使用して値を2 * PIラジアン未満に減らし、他の2つのルールで変更して、検索する適切なインデックスを見つける必要があります。Moduloは、整数と同じくらい速く固定小数点で動作します。

したがって、次のようなものを見ていることになります。

def sin(r):
    if r >= PI_BY_2:
        return sin (r % PI_BY_2)
    if r >= PI:
        return -sin (r - PI)
    if r >= PI_DIV_2:
        return sin (PI - r)
    return sin_lookup[r]
def cos(r):
    if r < PI_DIV_2:
        return sin (r + PI_DIV_2_BY_3)
    return sin (r - PI_DIV_2)

このcos関数は、実際には正弦から90度の位相シフトであるため、同じテーブルから余弦を取得するのがいかに安価であるかを示しています。

速度が非常に重要で、メモリが重要でない場合は、すべての範囲のインデックスを使用するだけで、計算は必要ありません。

もう1つのトリックは、使用するメモリを少なくして精度を犠牲にする場合は、すべての入力値のルックアップ値を格納しないことです。

正弦関数が滑らかな関数（不連続性がない）であるとすると、1つおきの値を格納し、その両側の値を平均するだけで、その間の値を補間できます。

たとえば、関数がある場合、実際の値と補間された値のテーブルが続きます（偶数の値のみを格納し、の奇数の値が補間され、以下でマークされているf(x) = x * xと仮定します）。xx*

 x    real f(x)   interpolated f(x)
--    ---------   -----------------
 0            0                   0
 1            1                   2 *
 2            4                   4
 3            9                  10 *
 4           16                  16
 5           25                  26 *
 6           36                  36
 7           49                  50 *
 8           64                  64
 9           91                  82 *
10          100                 100

f（x）値間の広がりは非常に大きくなる可能性があるため、これは完全な例ではありませんが、値が互いに近い関数の場合に適しています。

たとえば、sin（0）、sin（1）、およびsin（2）（ラジアンではなく度）の実数値は、0、0.017452406、および0.034899496です（これが勾配が最大になる場所です）。sin（0）とsin（2）の平均は0.017449748であり、これは実際の値から0.0152％の誤差であり、6,500分の1です。

したがって、エラーを最小限に抑えるために、メモリ要件を128Kの約5％、つまり6.5Kに半分にすることができます。

于 2009-11-15T04:50:23.673 に答える
1

最も速い方法は、それらを事前に計算してルックアップテーブルに保存することです。

もちろん、これはすべて、計算に期待する値の精度に依存します。詳細がいいでしょう。

于 2009-11-15T03:20:02.020 に答える