Next: , Previous: , Up: Root Extraction Algorithms   [Index]


15.5.2 N乗根

整数のN乗根は下記のようなNewton法による反復を行うことで得られます。 ここでAは入力値,nは指数を表わし,A^{1/n}を導出します。

         1         A
a[i+1] = - * ( --------- + (n-1)*a[i] )
         n     a[i]^(n-1)

初期値a[1]は,2進表現の“1"ビットごとにべき乗を行ってビット単位で生成し,真の根より大きくなるようにします。初期値が良ければ2乗オーダーで収束していきます。nが大きい時には,初期値の長さを大きく取ると収束状態が良くなります。現在の実装では特段最適化は行っていません。