代码

#include <iostream>
using namespace std;
const double eps = 1e-15;double sqrtByBisection(double n); // 第一种
double sqrtByNewton(double n); // 第二种
float sqrtHack(float x); // 第三种
float Q_rsqrt(float number); // 变形
float InvSqrt(float x); // 变形int main() {double num;cin >> num;//cout << sqrtByBisection(num);//cout << sqrtByNewton(num);//cout << sqrtHack(num);//cout << Q_rsqrt(num);cout << 1 / InvSqrt(num);return 0;
}double sqrtByBisection(double n) {if (n < 0) // 小于 0return n;double mid, last; // last 保存上一次的计算得到的 middouble low = 0, up = n;mid = (low + up) / 2;do{if (mid * mid > n) up = mid;else low = mid;last = mid;mid = (up + low) / 2; } while (abs(mid - last) > eps); // 精度控制return mid;
}double sqrtByNewton(double n) { // 牛顿迭代法double val = n;double last; // 保存上一次的值do {last = val;val = (val + n / val) / 2;		} while (abs(val - last) > eps);return val;
}/*
Quake-III Arena (雷神之锤3)是90年代的经典游戏之一。
该系列的游戏不但画面和内容不错，而且即使计算机配置低，
也能极其流畅地运行。
这要归功于它3D引擎的开发者约翰-卡马克（John Carmack）。
*/
float sqrtHack(float x)
{float xhalf = 0.5f * x;int i = *(int*)&x; // get bits for floating VALUE i = 0x5f375a86 - (i >> 1); // gives initial guess y0x = *(float*)&i; // convert bits BACK to floatx = x * (1.5f - xhalf * x * x); // Newton step, repeating increases accuracyx = x * (1.5f - xhalf * x * x); // Newton step, repeating increases accuracyx = x * (1.5f - xhalf * x * x); // Newton step, repeating increases accuracyreturn 1 / x;
}// 在game/code/q_math.c里发现了这样一段代码。
// 它的作用是将一个数开平方并取倒，经测试这段代码比(float)(1.0/sqrt(x))快4倍：
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 hackingi = 0x5f3759df - (i >> 1); // what the fuck?y = *(float*)&i;y = y * (threehalfs - (x2 * y * y)); // 1st iterationy = y * (threehalfs - (x2 * y * y)); // 2nd iteration, this can be removedy = y * (threehalfs - (x2 * y * y)); // 增加精确度#ifndef Q3_VM#ifdef __linux__assert(!isnan(y)); // bk010122 - FPE?#endif#endifreturn 1 / y;   // y 为平方根倒数
}float InvSqrt(float x)
{float xhalf = 0.5f * x;int i = *(int*)&x; // get bits for floating VALUE i = 0x5f375a86 - (i >> 1); // gives initial guess y0x = *(float*)&i; // convert bits BACK to floatx = x * (1.5f - xhalf * x * x); // Newton step, repeating increases accuracyx = x * (1.5f - xhalf * x * x); // Newton step, repeating increases accuracyx = x * (1.5f - xhalf * x * x); // Newton step, repeating increases accuracyreturn x;
}