数値計算の高速化 (cos, sin, exp)

質問

数値計算の計算コストに関しての質問です。

webなどで見ていると、「cos, sin, expは計算コストが
高く、高速化のために、他の計算方法で代用できる
場合は代用する」ということが書かれていたのを見ました。

cosやsinの計算にテイラー展開したもので代用する方が
計算が早くなるということでしょうか?

回答No.2

Oh-Orange · ベストアンサー

★乗算はテーブルにすると早い。
・2桁の『乗算』を『*』演算子で計算するよりも、10×10 のテーブルを
　用意して、テーブル参照させると高速になります。また、1桁の参照も
　別の1桁テーブル参照をさせると高速になります。→組み合わせる。
・このようにテーブルを用意して、固定小数点(整数値)で計算させると
　高速になります。→『多倍長演算』と呼び、マクローリン展開でどこ
　まで計算結果に精度を求めるかです。
・『マクローリン展開』でも収束するまで計算させるのではなく、回数を
　指定して 3～4 で強制的に計算を終了すれば高速になります。
・収束は倍・倍に精度がよくなるため、3～4 回の計算でも結構よい精度
　になりそうです。→試してみましょう。

最後に:
・よく使う数は、『定数』としてテーブルに保存して計算させると高速化
　できます。→『マクローリン展開』で利用する『階乗』など。(1!～6!)
・あと、実数値を多倍長の整数値で表現して、あとで小数点と桁数の丸め
　込みなどを行えば高速になります。→実数よりも整数が高速だから。
・『多倍長演算』で検索するといろいろ出てきます。
・以上。おわり。参考になりましたか？

リンク:
・http://yosshy.sansu.org/maclaurin.htm
・http://assam.cims.hokudai.ac.jp/~josch/workshop/math/Maclaurin/Maclaurin1.htm
・http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/math/diff/diff.htm

参考URL：

http://www5.airnet.ne.jp/tomy/cpro/longint.htm

お礼

回答ありがとうございます。

色々具体的に説明をしていただき感謝いたします。また、リンクの
情報もありがとうございます。

回答No.5

BearCave

No.4さんに同意。８ビット機時代ならともかく、現在はＦＰＵがある為、三角関数程度なら下手に近似計算するよりも高速だと思います。うちの会社（ゲーム開発）では普通に使っています。

回答No.4

rinkun

PCでやるなら自前で展開式を使っても高速にならないんじゃないかと思う。初等関数くらいはFPU命令であるし、i486以来FPUはCPU内蔵だからね。ソフトウェアで少々頑張ってもCPU内部で最適化されたハードウェア処理にはかなわないんじゃないかな。
# まずは初等関数命令の実行サイクルを確認しておいた方が良いと思う

PCでやる前提だと高速化に有効なのは低い精度で済む場合のテーブル参照くらいかな。これもキャッシュを乱して全体としては反って遅くなる場合もあるから要注意だけど。

なお多項式近似についてはマクローリン展開は最適ではないので、もっと効率的に計算できる展開係数がある。同じ精度を出すのに2,3項は減らせるんじゃなかったかな。
近似係数の計算法なんかは「近似式のプログラミング」などの書籍に載っていたと思う。

お礼

回答ありがとうございます。FPUで最適化されているということなのですね。

回答No.3

neKo_deux

> 例としまして、cos xをxの4乗までの計算精度でよい場合
> などは早くなるということでしょうか?
> (自分で速度を測ってみます。)

こちらは、処理系によりけりですので、測ってみるしか無いですね。
コストがかかるとは言っても、下手な計算アルゴリズムやコンパイラの最適化性能が悪いと、微妙です。

cos(x)のマクローリン展開にしても、Cの記述で、

例1：
y= 1 - x*x/2 + x*x*x*x/4*3*2 - x*x*x*x*x*x/6*5*4*3*2;
(xに関する乗算が9回、その他の乗算が6回)

例2：
double x2=x*x;
double x4=x2*x2;
double x6=x4*x2;
y = 1 - x2/2 + x4/24 - x6/720;
(xに関する乗算が3回、ただしdouble変数を確保する処理が3つ)

なんてテクニックも一般的です。
さすがに、最適化機能のあるコンパイラなら、定数の乗算はプリプロセッサあたりで処理されるハズですし、xの乗算についてもうまい事最適化するかもしれませんが…。

--
> ～テイラー展開でなく、
> そちらの近似式を使うと計算が早くなる」
> といったことなのだろうか? とも考えてました。

もちろん、そういう近似式もあるかも知れません。
必ずあるとは限らないし、特定の条件でしか成り立たない可能性もあります。
逆に、特定の条件を絞り込めるのなら、より良い近似があるかも知れません。

例：
sin(x)を、傾きが+1、-1の直線で場合分けして近似してしまうとか。
／＼／

--
No.2さんのような、テーブルを使う方法は有効です。

例：
ゲームの話ですが、敵や味方の動き、弾なんかの方向が36方向しか取らない、方向を整数型で持っているので360方向だなんて場合には、
cos(0°)
cos(1°)
・
・
cos(359°)
の360個のテーブルを持っておいても、メモリは大して圧迫されません。

お礼

あらためて詳細な説明ありがとうございます。

マクローリン展開の計算方法や、テーブルの利用に関して、必要な
精度で処理できるかなど検討してみます。

回答No.1

neKo_deux

> cosやsinの計算にテイラー展開したもので代用する方が
> 計算が早くなるということでしょうか?

どこまで展開するか？→どこまでの精度が必要か？次第です。
展開式が延々と続くなら必ずしも早くないし、計算結果も通常の取り扱いでは無視される精度で出てしまいます。

お礼

回答ありがとうございます。

例としまして、cos xをxの4乗までの計算精度でよい場合
などは早くなるということでしょうか?
(自分で速度を測ってみます。)

「インドの大数学者ラマヌジャンがπに関して考案したような
近似式がsinやcos, expにもあり、テイラー展開でなく、
そちらの近似式を使うと計算が早くなる」
といったことなのだろうか? とも考えてました。