2005年11月29日 (火) 09:51にMaintenance scriptによる

2005-11-29T09:51:58Z

Maintenance script: ページの作成:「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} - \ro...」

2005-11-29T09:07:10Z

ページの作成:「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} - \ro...」

新規ページ

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}

@@ 6行目: / 6行目: @@
 I.Newton法によるもの
-$$ x^2-a=0
+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

連続系アルゴリズム - 変更履歴

2005年11月29日 (火) 09:51にMaintenance scriptによる

Maintenance script: ページの作成:「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} - \ro...」

Maintenance script: ページの作成:「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} - \ro...」