整方根函数

整方根函数（Template:Lang-en），是指函数值为不大于自变量$a$的算术平方根的最大整数，定义域为自然数，符号表示为$\lfloor \sqrt{a}\rfloor$。

定义

整方根函数$\lfloor \sqrt{a}\rfloor$用原始递归函数可定义为：

$\{\begin{array}{c}\lfloor \sqrt{0}\rfloor =0\\ \lfloor \sqrt{Sa}\rfloor =\lfloor \sqrt{a}\rfloor +N(Sa\dot{-}(S\lfloor \sqrt{a}\rfloor {)}^2\end{array}$

牛顿法

由牛顿法迭代公式$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_{n+1})}$，欲计算$\lfloor \sqrt{a}\rfloor$，可令

$f(x)=x^2-a$，由$x^2-a=0$，得

$f(x)$与$x$轴相交于$x=\sqrt{a}$，可计算平方根，于是

$f^{\prime }(x)=2x$，代入迭代公式可得

$x_{n+1}=x_n-\frac{x_n^2-a}{2x_n}$，整理得

$x_{n+1}=\frac{x_n}{2}+\frac{a}{2x_n}$。

算法结束条件为${\mathrm{\Delta }}_n=|x_{n+1}-x_n|=0$，即$x_{n+1}=x_n$。