查看“︁整方根函数”︁的源代码

'''整方根函数'''（{{lang-en|integer square root function}}），是指函数值为不大于自变量<math>a</math>的[[算术平方根]]的最大整数，定义域为[[自然数]]，符号表示为<math>\lfloor\sqrt{a}\rfloor</math>。<ref name=":0">{{Cite book|title=数学辞海 第四卷. 第四卷|url=https://www.worldcat.org/title/shu-xue-ci-hai-di-si-juan/oclc/952671770&referer=brief_results|publisher=[[山西教育出版社]]等|date=2002|location=[[太原]]|isbn=978-7-5440-2400-6|oclc=952671770|last=何思谦|last2=徐利治|access-date=2021-12-19|archive-date=2020-02-20|archive-url=https://web.archive.org/web/20200220044037/https://www.worldcat.org/title/shu-xue-ci-hai-di-si-juan/oclc/952671770%26referer%3Dbrief_results|dead-url=no}}</ref>

== 定义 ==
整方根函数<math>\lfloor\sqrt{a}\rfloor</math>用[[原始递归函数]]可定义为：<ref name=":0" />

<math>\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}</math>

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

<math>f(x)=x^2-a</math>，由<math>x^2-a=0</math>，得

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

<math>f'(x)=2x</math>，代入迭代公式可得

<math>x_{n+1}=x_n-\frac{x_n^2-a}{2x_n}</math>，整理得

<math>x_{n+1}=\frac{x_n}{2}+\frac{a}{2x_n}</math>。

算法结束条件为<math>\Delta_n=\left\vert x_{n+1}-x_n \right\vert=0</math>，即<math>x_{n+1}=x_n</math>。<ref>{{Cite book|title=微電腦程式的作法|url=https://www.worldcat.org/title/wei-dian-nao-cheng-shi-de-zuo-fa/oclc/818401959&referer=brief_results|publisher=王家|date=1980|location=[[臺南市]]|oclc=818401959|last=賴耿陽|page=127-130|access-date=2021-12-19|archive-date=2020-02-20|archive-url=https://web.archive.org/web/20200220104525/https://www.worldcat.org/title/wei-dian-nao-cheng-shi-de-zuo-fa/oclc/818401959%26referer%3Dbrief_results|dead-url=no}}</ref>

== 参考资料 ==
{{reflist}}

{{数论算法}}
[[Category:数论算法]]
[[Category:数论]]
[[Category:求根算法]]