連続系アルゴリズム

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}の初期値が用意できれば、”３回”でよい。 正規化： 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} １回：2^{-26} ２回：2^{-13] ３回：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}