整方根函数

✍ dations ◷ 2025-07-11 07:31:27 #数论算法,数论,求根算法

整方根函数(英语:integer square root function),是指函数值为不大于自变量 a {\displaystyle a} 的算术平方根的最大整数,定义域为自然数,符号表示为 a {\displaystyle \lfloor {\sqrt {a}}\rfloor }

整方根函数 a {\displaystyle \lfloor {\sqrt {a}}\rfloor } 用原始递归函数可定义为:

{ 0 = 0 S a = a + N ( S a ˙ ( S a ) 2 {\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}}}

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

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

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

f ( x ) = 2 x {\displaystyle f'(x)=2x} ,代入迭代公式可得

x n + 1 = x n x n 2 a 2 x n {\displaystyle x_{n+1}=x_{n}-{\frac {x_{n}^{2}-a}{2x_{n}}}} ,整理得

x n + 1 = x n 2 + a 2 x n {\displaystyle x_{n+1}={\frac {x_{n}}{2}}+{\frac {a}{2x_{n}}}}

算法结束条件为 Δ n = | x n + 1 x n | = 0 {\displaystyle \Delta _{n}=\left\vert x_{n+1}-x_{n}\right\vert =0} ,即 x n + 1 = x n {\displaystyle x_{n+1}=x_{n}}

相关

  • 布鲁斯特·卡利布鲁斯特·卡利(Brewster Kahle /ˈkeɪl/ KAYL-'; 1960年-) 是一位美国数字图书馆员、电脑工程师和资讯科技企业家,是Alexa Internet和互联网档案馆的创始人。 2012年入选互联网
  • 小油坑坐标:25°10′31.33″N 121°32′50.84″E / 25.1753694°N 121.5474556°E / 25.1753694; 121.5474556小油坑是位于台湾北部阳明山国家公园内的一处火山喷气孔,位于七星山西
  • 劳动人口劳动人口是经济学上对能够被雇佣(劳动)潜力的社会人群(人口)指称。在法制健全的国家,能够合法被雇佣的年龄有严格的法律规定,一般规定允许工作的年龄下限,以及退休年龄;对所有能够被
  • Schedule III《受管制药物和物品法》(英语:Controlled Drugs and Substances Act,法语:Loi réglementant certaines drogues et autres substances)是加拿大的联邦药物管制法令,于1996年在首
  • 哈瓦苏湖城哈瓦苏湖城(英语:Lake Havasu City),是美国亚利桑那州莫哈维县下属的一座城市。 面积约为44.48平方英里(约合115.2平方公里)。根据2010年美国人口普查,该市有人口52,527人,人口密度
  • 影片 (消歧义)影片可能指:
  • 高压共轨高压共轨燃油直喷(Common rail direct fuel injection)是汽油机与柴油机的一种燃油直喷技术。对于柴油机,燃油压力高达1,800 bar或180 MPa或26,000 psi,引擎运转时高压共轨使
  • 克里斯·孔斯克里斯托弗·安德鲁·“克里斯”·孔斯(英语:Christopher Andrew "Chris" Coons;1963年9月9日-),是一位美国民主党政治人物,现任德拉瓦州美国参议院议员、前纽卡斯尔县县长及前纽卡
  • 明安达礼明安达礼(满语:ᠮᡳᠩᡤᠠᠨᡩᠠᡵᡳ,穆麟德:,?-1669年),蒙古正白旗人,西鲁特氏,世居科尔沁。清朝政治人物、清朝兵部尚书。世袭游击将军,兼牛录额真。崇德三年,任巴牙喇甲喇章京。六年,进
  • 林维朝林维朝(1868年-1934年),字德卿,号翰堂,别署怡园主人,是台湾嘉义新港人。他是清末秀才,日治时期亦参与嘉义政治事务,担任过嘉义厅参事。此外他也重视地方文教,在登云书院倒塌后,于怡园开