|
数学関数 |
|
実数指数(Exp) |
| 最終更新日：2006/06/16 内容見直し |
●概要
指数が実数の場合は、単純な累乗計算では求められなく、級数展開を利用する。
2006/6/12 に、Exp演算シミュレータ(実測しないで実環境での演算時間をシミュレーションできるツール)を作成したので、改めて、Expの方式を検討した。想定できる殆どの手法の得失を、100万桁まで短時間に予測可能となった。
●指数関数の基本
○級数
eX = ∑(Xk / k!) [ k = 0 to ∞]
から求める。
●1/N
○原理
実数指数 X は、
X = I + F 但し、I は、X の整数部、F は、X の小数部
とできるので、
eX = e(I + F)
= eI *
eF
となるが、eI は、整数指数なので、単純な乗算で求められる。結局、eF を求めることに帰着する。しかも、F は、0 =< F < 1 の限定された範囲となり、級数の収束に大いに貢献する。更に、
F = u * N (N は、正整数)
とすれば、u = F / N なので、
eF = e(u*N) = (eu)N
とでき、最終的には、eu を求めることになる。N は任意であるが、あまり大きくすると、N乗計算に時間が掛かってしまう。
○2進か10進か？
N として、10m か 2m にするか迷うところである。10進数では、1/N は、指数部の調整で済むが、２進数では、除算が必要となり、場合によっては、1/Nにより冪数の桁が長くなるので不利になる。しかし、冪乗の乗算回数は、２進数の場合は少なくて済む（平均10進の場合の2/3）。このことをツールで1/Nと冪乗時間を各公称精度でシミュレーションしてみると、下図が得られた。
当初、2進が良いと単純に思い込んでいたが、シミュレーション結果では、さほどの差はないと出た。精度が高い方ではむしろ、10進の方が速い。除算が不要な10進を採用する。但し、冪乗の回数が多い分、2進より演算精度が落ちる。
○N の値は？
除算が不要な 10m を採用するが、m の最適値を見つける。これについてもツールでシミュレーションした。変数のオーダ、桁数などでも複雑に変化する。
・変数が長い場合
下図は、変数オーダが 0 で、桁数が公称精度の場合の N の大きさに対する効果である。
級数直は、変数をそのままで級数展開した場合の演算時間で、これより短ければ効果ありとなる。結果には、N冪乗時間も加算されている。結果を見る限り、N が大きければ大きいほど効果が見られる。数倍の速度効果が期待できる。
・変数が短い場合
下図は、変数オーダが 0 で、桁数が8桁の場合である。
N が大きければ大きいほど効果が見られる。同じく数倍の効果。少なくとも、変数のオーダが 0 のとき、1018 を採用する。
●指数分割
○原理
eu において、u = u0 + u1 + u2 + u3 + ・・・ + uk であれば、
eu = e(u0 + u1 + u2 + u3 + ・・・ + uk)
= eu0・eu1・eu2・eu3・・・・・euk
と、各項の乗積で求められる。もし、各項が頗る早く求められ、その各項時間と乗積時間の和が eu の時間より短ければ高速化できる。
○方法
級数の演算時間は、Xk の計算が支配的となるが、この乗算は、
Xk = X(k-1)・X
となり、もし X の桁数が数十桁以内と短ければ、MulI、MulS で実行され、FMul より頗る短い時間となる。最初のポイントはここである。
今、例えば指数 u を下図のように、d桁づつ頭より4+1分割する。
つまり、u = u0 + u1 + u2 + u3 + u4 とする。これにて、各指数は概ね、d桁の短い値となり、各次数は、d 単位で減少する。次数の減少は級数の収束を早めることになる。これが第二のポイントである。
今例えば、p = 0 、d = 32 、公称精度を32768桁とすれば、下表のような収束/乗算時間表となる。
| 指数 | u0 | u1 | u2 | u3 | u4 |
| 指数の次数 | 0 | -32 | -64 | -96 | -128 |
| 項目数 | 9275 | 949 | 495 | 335 | 253 |
| 乗算時間 | 25S | 2.5S | 1.3S | 1S | 7.3S |
u4 の時間はフル精度乗算時間となる
上記の時間の総和に乗積時間 0.1S を加えると、37S となるが、そのまま求めた eu の時間は、267S なので、分割方式の方が速くなる。加減算やDivI時間を考慮しても傾向は同じなので、分割法は有効と言える。
○予測
ツールで分割法の効果を予測すると下図が得られた。下図は、分割数を16に固定して、公称精度毎の分割桁(8～40)に対する効果である。1/N は実施しない場合である。列1/N は、分割法を適用しなかった時間、その他はそれぞれの分割桁に対する時間となっている。薄緑の背景色の部分はその公称精度での最小時間である。
精度の高い部分では10倍以上の高速化ができている。しかし、分割数、分割桁、変数オーダ、1/N の状態などにより時間が最小になる状態は一定しなく、複雑に変化する。
下図は、特定の変数の状態における、時間が最小になる分割数と分割桁をツールにて自動的に探索した結果である。
下図は、公称精度が32768 の場合の、分割数と分割桁の二次元マップで、薄緑色が最小値である。上記結果と合っている。
現実の変数は、オーダ、有効桁数が広い範囲で分布し、全てに対して最適分割法は適用できない。結局、エイヤッと決めるしかない。