当前位置 博文首页 > dadalaohua的博客:【学习笔记】牛顿迭代法求平方根倒数
介绍使用牛顿迭代法求平方根倒数 1 x \frac{1}{\sqrt{x}} x?1?的C语言实现和公式的推导。
float InvSqrt(float num)
{
float x = 1/num;
float xhalf = 0.5f * num;
float error = 1e-5;
while (fabs(1.0f - num * x * x) >= error)
{
x = x*(1.5f-(xhalf*x*x));
}
return x;
}
代码很简单,就是使用牛顿迭代法计算,然后判断是否达到想要的精度,达到精度后退出。
这里精度设置是0.00001,可以根据自己实际情况调整。
传进来的值num
必须大于0。
可以加入一个判断防止传入的值小于等于0.
float InvSqrt(float num)
{
if (num > 0)
{
float x = 1/num;
float xhalf = 0.5f * num;
float error = 1e-5;
while (fabs(1.0f - num * x * x) >= error)
{
x = x*(1.5f-(xhalf*x*x));
}
return x;
}
else
{
return -1;
}
}
这里说明代码x = x*(1.5f-(xhalf*x*x));
是如何得到的。
牛顿迭代法公式如下。
x n + 1 = x n ? f ( x n ) f ′ ( x n ) x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} xn+1?=xn??f′(xn?)f(xn?)?
我们计算平方根倒数的公式:
y = 1 x = x ? 1 2 y = \frac{1}{\sqrt{x}} = x^{-\frac 12} y=x?1?=x?21?
所以
1 y 2 = x \frac{1}{{y}^2} = x y21?=x
构建以y为自变量的函数方程为
f ( y ) = 1 y 2 ? x = 0 f(y) = \frac{1}{{y}^2} - x = 0 f(y)=y21??x=0
? = y ? 2 ? x = 0 = {{y}^{-2}} - x = 0 =y?2?x=0
f ′ ( y ) = ? 2 y ? 3 = 0 f'(y) = {{-2}{y}^{-3}} = 0 f′(y)=?2y?3=0
将 f ( y ) f(y) f(y)和 f ′ ( y ) f'(y) f′(y)带入
y ? f ( y ) f ′ ( y ) = y ? y ? 2 ? x ? 2 y ? 3 y - \frac{f(y)}{f'(y)} = y - \frac{