整方根函數

整方根函數（英語：integer square root function），是指函數值為不大於自變量${\displaystyle a}$的算術平方根的最大整數，定義域為自然數，符號表示為${\displaystyle \lfloor {\sqrt {a}}\rfloor }$。^[1]

定義

整方根函數${\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]