c - 正弦ルックアップ テーブルからの逆正弦計算の効率

Question

システムでサイン/コサイン値を計算するルックアップ テーブルを実装しました。逆三角関数 (arcsin/arccos) が必要になりました。

私のアプリケーションは、プログラム メモリが限られているため、arcsin の 2 番目のルックアップ テーブルを追加できない組み込みデバイスで実行されています。したがって、私が考えていた解決策は、サイン ルックアップ テーブルを参照して、対応するインデックスを取得することでした。

このソリューションは、数学標準ライブラリからの標準実装を使用するよりも効率的かどうか疑問に思っています。
誰かがすでにこれを実験しましたか？

LUT の現在の実装は、0 から PI/2 までの正弦値の配列です。テーブルに格納された値は 4096 で乗算され、アプリケーションに十分な精度を持つ整数値のままになります。1/4096 の解像度のルックアップ テーブルで、6434 個の値の配列が得られます。次に、引数として4096を掛けたラジアンの角度をとる2つの関数正弦と余弦があります。これらの関数は、指定された角度を第 1 象限の対応する角度に変換し、表の対応する値を読み取ります。

私のアプリケーションは dsPIC33F で 40 MIPS で動作し、C30 コンパイル スイートを使用しています。

Answer 1

C++ をサポートしない C30 コンパイラを使用しなければならないのはおそらく残念です。それ以外の場合は、固定小数点演算とその関連ライブラリを使用した数学集約型アプリケーションの最適化を参照してください。

ただし、 CORDIC アルゴリズムの一般原則が適用され、メモリ フットプリントは現在の実装よりもはるかに小さくなります。この記事では、arctan() の生成について説明し、arccos() および arcsin() は、ここで説明されているように、そこから計算できます。

もちろん、平方根と除算も必要になることも示唆しています。PIC24/dsPIC にはハードウェア整数除算がありますが、これらは高価な場合があります。数学アクセラレーションに関する記事では、平方根も扱っています。ルックアップ テーブル アプローチは、直接ルックアップでは高速になる可能性がありますが、逆検索ではおそらくそうではありませんが、この記事で説明するアプローチはより一般的で正確です (ライブラリは 64 ビット整数を 36.28 ビットとして使用します)。固定小数点を使用すると、アプリケーションの精度と範囲が少なくなる可能性があります)、ソフトウェア浮動小数点を使用した標準ライブラリの実装よりも確実に高速です。

Answer 2

粗粒度のルックアップテーブルを組み合わせてメモリを節約する「中間」アプローチと、中間値の数値近似を使用できます（たとえば、線形補間よりも正確なMaclaurin級数）。

ここにいくつかの例があります。

この質問には、いくつかの関連リンクもあります。

Answer 3

6434 の二分探索では、値を見つけるために約 12 回のルックアップが必要になり、さらに精度が必要な場合は補間が続きます。正弦曲線の性質により、一方の端で他方の端よりもはるかに高い精度が得られます。メモリを節約できる場合は、入力に均等に配置された独自の逆テーブルを作成すると、速度と精度が向上する可能性があります。

組み込みバージョンとの比較に関しては、それをテストする必要があります。その際、画像のサイズがどれだけ大きくなるかに注意してください。stdin の実装は、一部のシステムではかなり重くなる可能性があります。