整方根函數

整方根函數（英語：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}$。