整方根函数

整方根函数（英語：integer square root function），是指函数值为不大于自变量$a$的算术平方根的最大整数，定义域为自然数，符号表示为$\lfloor {\sqrt {a}}\rfloor$。

定义

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

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

牛顿法

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

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

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

$f'(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}}}$。

算法结束条件为$\Delta _{n}=\left\vert x_{n+1}-x_{n}\right\vert =0$，即$x_{n+1}=x_{n}$。