連続系アルゴリズム

提供: IS2005 Wiki
移動: 案内検索

11/28 連続系

普通関数 log, exp, sin, cos, tan, arctan, sqrt

I.Newton法によるもの x^2-a=0 x_{n+1} = \frac{1}{2}(x_n+\frac{a}{x_n}) x_{n+1} - \root{a} = \frac{1}{2x_n}(x_n-\root{a})^2 相対誤差:\frac{x_{n+1}-\root{a}}{\root{a}}=\frac{\root{a}}{2x_n}(\frac{x_m-\root{a}}{\root{a}})^2

※x_{n+1} = x_n - \frac{1}{2}(x_n-\frac{a}{x_n})  とすると、1bit精度が良くなる

32bit IEEE: \epsilon_m = 2^{-24} N回Newton法を適用することを考える。 |\frac{x_N-\root{a}}{\root{a}}| ~~ 2^{-2x} N-1 ~~ 2^{-12} N-2 ~~ 2^{-6}

2^{-6}の初期値が用意できれば、”3回”でよい。 正規化: a = 1.f * 2^{e-127} eが奇数(1-253) \root{a} = \root{1.f}2^\frac{e-127}{2} eが偶数 \root{a} = \root{2*1.f}2^\frac{e-127}{2}

64bit IEEE \epsilon_M = 2^{-53} 1回:2^{-26} 2回:2^{-13] 3回:2^{-6}

初期値の別の求め方 多項式を使う(単精度では多項式、倍精度では一回Newton法を用いる)

II.多項式近似 log,exp,sin,cos,tan,tan^{-1} !全区間を多項式で表現することはできない (sin,cosはどの区間でも値域は-1から1の間だが、どんな多項式も発散するから) →基本区間への変換(が必要) sin関数 基本区間を-\frac{\pi}{2}〜\frac{\pi}{2}とする。 (公式) n:整数 \sin(2\pin+x) = \sin(x) \sin(\frac{\pi}{2}-x) = \sin(\frac{\pi}{2}+x)

x:radian \sin(x) : x は任意の実数 x_1 = \frac{2}{\pi}x x_2 = x + 2\pi└\frac{x_1+1}{4}┘(切捨て)(-\frac{\pi}{2}<=x2<\frac{3\pi}{2}) x_3 = \frac{2}{\pi}x_2 (-1<= x3 < 3) if x_3 > 2 then x_3 = 1 - x_3(-1<=x3<1)

丸め誤差の減少(倍精度を基本とする) |x|が大きいと、x_2に桁落ちがおこりやすい。 そこで、通称三倍精度を用いる。 x_2 = x - 2\pi \times n 特徴: 2\pi : 定数 n : 整数 2\pi = p_1 + p_2 p_1 = 6.28....|000000(合計52bit) p_2 = 0.000000|......(後ろの...が52bit) x_2 = (x - p_1 \times n) - p_2 \times n

sin(\frac{\pi}{2}x_3) = x_3P(x_3^2) P:(近似)多項式 Pの次数が 3: 近似誤差は7*10^{-7} 4: 4*10^{-9} 5: 1.7*10^{-11}

基本区間の幅 vs 多項式の次数   大        大   小        小 そこで、sin,cosの基本区間を-\frac{\pi}{4}から-\frac{\pi}{4}とすると、 sin,cosのどちらかを使えば値が計算でき、幅が小さくなったので次数が小さくなる。

exp: e^x = 2^y y = xlog_2e y = y_1 + y_2 (y_1:整数、0<=y_2<1)

y_1 = └y┘ y_2 = y - y_1(このとき、三倍精度の技が使える)

2^{y_1+y_2} = 2^{y_1}2^{y_2} 2^{y_2} = P(y_2-\frac{1}{2}) Pへの引数は[-1/2,1,2) = 1.f Pの次数が 3: 最大誤差1.1*10^{-4} 4: 3.7*10^{-6} 5: 1.1*10^{-7} 6: 2.6*10^{-7}

2^{y_1}を指数部、fを仮数部とすればよい。

log x x = 1.f * 2^{e-hoge} x_1 = e - hoge x_2 = 1.f (1 <= x_2 < 2) log x = log 2 * x_1 + log x_2 log x_2 = P(x_2) Pの次数が 6: 10^{-6} 9: 10^{-9}