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が大きい時には，初期値の長さを大きく取ると収束状態が良くなります。現在の実装では特段最適化は行っていません。