当前位置 博文首页 > dadalaohua的博客:【学习笔记】使用魔数快速求立方根
介绍使用魔数0x2a517d47快速求立方根 x 3 {\sqrt[3]{x}} 3x?的C语言实现和公式的推导。
float MagicCubeRoot(float x)
{
float xthird = 0.333f * x;
int i = *(int*)&x;
i = (0x2a517d47 + (0.333f * i));
x = *(float*)&i;
x = 0.667f * x + xthird / (x * x);
return x;
}
代码用于快速计算立方根 x 3 {\sqrt[3]{x}} 3x?。
代码中核心部分是
i = (0x2a517d47 + (0.333f * i));
该行代码就完成了计算立方根。
另外再使用一次牛顿迭代法提高下精度
x = 0.667f * x + xthird / (x * x);
所以整个计算过程就是
1.i = *(int*)&x;
将输入的数转换成整数
2.i = (0x2a517d47 + (0.333f * i));
通过魔数完成立方根的计算。
3.x = *(float*)&i;
转换回浮点数。
4.x = 0.667f * x + xthird / (x * x);
使用一次牛顿迭代法提高下精度。
完成快速计算立方根 x 3 {\sqrt[3]{x}} 3x?。
如果需要提高精度,可以多进行一次牛顿迭代。
float MagicCubeRoot(float x)
{
float xthird = 0.333f * x;
int i = *(int*)&x;
i = (0x2a517d47 + (0.333f * i));
x = *(float*)&i;
x = 0.667f * x + xthird / (x * x);
x = 0.667f * x + xthird / (x * x);
return x;
}
注意,上面的函数只支持正数,传进来的值x
需要大于或等于0。
如果要支持负数,可以增加如下判断处理。
float MagicCubeRoot(float x)
{
if (x < 0)
{
x = -x;
float xthird = 0.333f * x;
int i = *(int*)&x;
i = (0x2a517d47 + (0.333f * i));//i = (int) (0x2a517d3c + (0.333f * i));
x = *(float*)&i;
x = 0.667f * x + xthird / (x * x);
//x = 0.667f * x + xthird / (x * x);
x = -x;
}
else
{
float xthird = 0.333f * x;
int i = *(int*)&x;
i = (0x2a517d47 + (0.333f * i));//i = (int) (0x2a517d3c + (0.333f * i));
x = *(float*)&i;
x = 0.667f * x + xthird / (x * x);
//x = 0.667f * x + xthird / (x * x);
}
return 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 = x 3 = x 1 3 y = {\sqrt[3]{x}} = x^{\frac 13} y=3x?=x31?
所以
y 3 = x {{y}^3} = x y3=x
构建以y为自变量的函数方程为
f ( y ) = y 3 ? x = 0 f(y) = {{y}^3} - x = 0 f(y)=y3?x=0