ニュートン-ラプソン除算
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/26 11:07 UTC 版)
「除算 (デジタル)」の記事における「ニュートン-ラプソン除算」の解説
ニュートン-ラプソン除算 (Newton-Raphson Division) は、ニュートン法を用いて D {\displaystyle D} の逆数を求め、その値と N {\displaystyle N} の乗算を行うことで商 Q {\displaystyle Q} を求める。 ニュートン-ラプソン除算のステップは次の通り。 除数 ( D {\displaystyle D} ) の逆数の近似値を計算する: X 0 {\displaystyle X_{0}} 逆数のより正確な近似値を反復的に計算する: ( X 1 , … , X S ) {\displaystyle (X_{1},\ldots ,X_{S})} 被除数と除数の逆数の乗算を行うことで商を計算する: Q = N X S {\displaystyle Q=NX_{S}} D {\displaystyle D} の逆数をニュートン法で求めるには、 X = 1 / D {\displaystyle X=1/D} で値がゼロとなる関数 f ( X ) {\displaystyle f(X)} を求める必要がある。明らかにそのようになる関数としては f ( X ) = D X − 1 {\displaystyle f(X)=DX-1} があるが、これは D {\displaystyle D} の逆数が既にわかっていないと使えない。さらに f ( X ) {\displaystyle f(X)} の高次導関数が存在しないため、反復によって逆数の精度を増すこともできない。実際に使用できる関数は f ( X ) = 1 / X − D {\displaystyle f(X)=1/X-D} で、この場合のニュートン-ラプソンの反復は次の式で表される。 X i + 1 = X i − f ( X i ) f ′ ( X i ) = X i − 1 / X i − D − 1 / X i 2 = X i + X i ( 1 − D X i ) = X i ( 2 − D X i ) {\displaystyle X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i})} この場合、 X i {\displaystyle X_{i}} から乗算と減算だけで計算可能であり、積和演算2回でもよい。 誤差を ϵ i = D X i − 1 {\displaystyle \epsilon _{i}=DX_{i}-1\,} と定義すると X i = 1 D ( 1 + ϵ i ) {\displaystyle X_{i}={1 \over D}(1+\epsilon _{i})\,} ϵ i + 1 = − ϵ i 2 {\displaystyle \epsilon _{i+1}=-{\epsilon _{i}}^{2}\,} となる。 除数 D が 0.5 ≤ D ≤ 1 となるようビットシフトを施す。同じビットシフトを被除数 N にも施せば、商は変化しない。すると、ニュートン-ラプソン法の初期値として次のような線形近似が使える。 X 0 = T 1 + T 2 D ≈ 1 D {\displaystyle X_{0}=T_{1}+T_{2}D\approx {\frac {1}{D}}\,} 区間 [ 0.5 , 1 ] {\displaystyle [0.5,1]} においてこの近似の誤差の絶対値をなるべく小さくするには、次の式を使用する。 X 0 = 48 17 − 32 17 D {\displaystyle X_{0}={48 \over 17}-{32 \over 17}D\,} [要出典] この近似を用いると、初期値の誤差は次のようになる。 | ϵ 0 | ≤ 1 17 ≈ 0.059 {\displaystyle \vert \epsilon _{0}\vert \leq {1 \over 17}\approx 0.059\,} この技法の収束は正確に二次的なので、 P {\displaystyle P\,} 桁の二進数の値を計算する場合のステップ数は次のようになる。 S = ⌈ log 2 P + 1 log 2 17 ⌉ {\displaystyle S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}
※この「ニュートン-ラプソン除算」の解説は、「除算 (デジタル)」の解説の一部です。
「ニュートン-ラプソン除算」を含む「除算 (デジタル)」の記事については、「除算 (デジタル)」の概要を参照ください。
- ニュートン-ラプソン除算のページへのリンク
