ニュートン法

多倍長演算ライブラリ(UltraPrecision)

ニュートン法

最終更新日：2006/06/23 新規

●概要

　これまで、逆数、平方根、立方根はニュートン法であったが、個別に検討してきた。一通り開発ができたので、整理してみると、全て同じ理屈で高速化しているので、ここにまとめて見た。

●高速化原理

　ニュートンにおける高速化は、

の二つとなる。漸化式の次数は、逆数でのみ採用できる方法となるので、ここでは、次数を 2 にして、初期値問題を統一的に述べて見る。

●収束

○関係式

　一般に、ニュートンで求められる精度桁数は、以下の式となる。

　　　d_n = 2ⁿ・d₀d_n は、n 回目の精度桁数、d₀ は初期値桁数

変形して、2の対数を取ると、

　　　n = log₂(d_n) - log₂(d₀)

と、収束回数が、目標精度と初期値精度で表せる。上式は、初期値精度が倍になれば、収束回数が1回減少することを表している。下図は、初期値桁数を16～246までの場合の収束回数をプロットしたグラフである。

次数 2 の場合の収束状況

○初期値と収束

　初期値を16桁から開始すると、16回掛かる場合でも、初期値を目標精度の1/8 の桁から開始すれば、理屈では 3回で収束する。しかし、1/8 の初期値を求めるのに 13回掛かるので合計の収束回数は同じとなる。でも、

となるので、演算時間が短くなる可能性を持っている。ニュートン漸化式では除算がなければ乗算が支配的となるので、乗算係数(乗算時間の傾向を示す値)を算出して見る。

　100万桁の場合とする。100万桁の乗算時間は、3S、1/8 の13万桁では、0.14S として算出。

となる。初期値が、1/8 の場合、乗算係数は小さくなる。つまり、演算時間が短くなる可能性がある。

　一般的に表せば、高速化条件は、

　　t_a・n_a + t_b・n_b ＜ t_b・N

但し、n_a+ n_b = N、t はその精度における演算時間、N はトータルの収束回数

となる。n_a+ n_b = N を代入して解くと、

　　　t_a ＜ t_b(n_a ≠ 0)

と、初期値を求める単位時間(ループ当りの演算時間)が目標精度におけるそれより短ければ、一般的に成立する。しかし、最も効果のある初期値は一般的には求められない。

●多段初期値

　1/8 の初期値を求める時間は、さらにその1/8 の初期値から求めれば短くなる。これを繰り返せば、さらに短くなる可能性がある。つまり、

　∑(t_pi・n_i) ＜ t_pk・N [i = 0 to k]

但し、∑n_i= N、t_pi は精度pi における演算時間、N はトータルの収束回数

になる、n の分割方法が存在するかも知れない。

●シミュレーション

　理屈で効果があると分かっても、いきなり実際に確かめるのはムダになるかも知れないし、精度が高くなると時間が掛かってしまう。そこで、シミュレータを開発した。次数、初期値、多段初期値について、100万桁までの演算時間をシミュレーションするものである。これについてはそれぞれの頁で解説する。