整方根函数

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

整方根函数${\displaystyle \lfloor <!--\; \lfloor \; -->\sqrt{a}\rfloor <!--\; \rfloor \; -->}$用原始递归函数可定义为：

${\displaystyle \{\begin{array}{l}\lfloor <!--\; \lfloor \; -->\sqrt{0}\rfloor <!--\; \rfloor \; -->=0\\ \lfloor <!--\; \lfloor \; -->\sqrt{Sa}\rfloor <!--\; \rfloor \; -->=\lfloor <!--\; \lfloor \; -->\sqrt{a}\rfloor <!--\; \rfloor \; -->+N(Sa\stackrel{\dot{}<!--\; \dot{}\; -->}{-<!--\; -\; -->}(S\lfloor <!--\; \lfloor \; -->\sqrt{a}\rfloor <!--\; \rfloor \; -->{)}^2\end{array}}$

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

${\displaystyle f(x)=x^2-<!--\; -\; -->a}$，由${\displaystyle x^2-<!--\; -\; -->a=0}$，得

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

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

${\displaystyle x_{n+1}=x_n-<!--\; -\; -->\frac{x_n^2-<!--\; -\; -->a}{2x_n}}$，整理得

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

算法结束条件为${\displaystyle {\mathrm{\Delta <!--\; \Delta \; -->}}_n=\left|x_{n+1}-<!--\; -\; -->x_n\right|=0}$，即${\displaystyle x_{n+1}=x_n}$。