警示后人&一种不一样的解题思路

首先警示后人，如果你用牛顿迭代，千万别写出类似const double twothird = 0.66667;这样的唐氏东西，这个玩意精度差一点会严重影响最终结果导致会炸掉（别问我怎么知道的）。

然后是一种不一样的解题思路。《雷神之锤Ⅲ》里有一种著名的平方反根算法，也就是这个：

CPP

float Q_rsqrt( float number )
{
	long i;
	float x2, y;
	const float threeHalfs = 1.5f;

	x2 = number * 0.5f;
	y  = number;
	i  = * ( long * ) &y;                       // evil floating point bit level hacking
	i  = 0x5f3759df - ( i >> 1 );               // What the fuck? 
	y  = * ( float * ) &i;
	y  = y * ( threeHalfs - ( x2 * y * y ) );   // 1st iteration
//	y  = y * ( threeHalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

	return y;
}

我们其实可以有一种类似的算法求立方根：

CPP

double Q_cbrt(double number)
{
	long long i;
	double x2, y;
	const double twothird = 2.0 / 3;
	x2 = number * 0.5;
	y = number;
	i = * (long long *) &y;   
	i = 3071319837877857280ll + i / 3;     
	y = * (double *) &i;
	y = twothird * (y + x2 / y / y);
	y = twothird * (y + x2 / y / y);
	y = twothird * (y + x2 / y / y);
    y = twothird * (y + x2 / y / y);
	return y;
}

当然这个算法的效率比平方反根是差不少的，因为用了很多除法运算。但是它依然是高贵的

O(1)

时间复杂度——虽然结果是近似的就是了……

警示后人&一种不一样的解题思路

讨论操作

回复

相关推荐

警示后人&一种不一样的解题思路