整方根函数

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

${\displaystyle {\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}}}$ 

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

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

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

${\displaystyle f'(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 \Delta _{n}=\left\vert x_{n+1}-x_{n}\right\vert =0}$ ，即${\displaystyle x_{n+1}=x_{n}}$ 。^[2]