《雷神之锤III竞技场》使用的平方根倒数速算法
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（对浮点数的邪恶位元hack）
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;
}
自行尝试去理解这段代码好几次都失败了，最后在看到这篇文章（0x5f3759df这个快速开方中的常数的数学依据是什么？）之后才算理解。为了验证自己是不是真的理解，写了一个js版。并写了一个测试用例跟js内置的开方函数进行对比，可以看到相对误差在千分之2以内。
(() => {
const buffer = new ArrayBuffer(8);
const view = new DataView(buffer);
// 求平方根
function sqrt(x) {
return 1 / Q_rsqrt(x);
}
// 平方根倒数
function Q_rsqrt(number) {
// let i;
let x2, y;
const threehalfs = 1.5;
x2 = number * 0.5;
y = number;
// i = * ( long * ) &y; // evil floating point bit level hacking
view.setFloat64(0, number, true);
let low = view.getUint32(0, true);
let high = view.getUint32(4, true);
// i = 0x5fe6eb50c7aa19f9 - ( i >> 1 ); // what the fuck?
low = low >> 1;
let odd = (high % 2) === 1;
if (odd) {
low += 0x80000000;
}
high = high >> 1;
high = 0x5fe6eb50 - high;
low = 0xc7aa19f9 - low;
if (low < 0) {
high--;
low += 4294967296;
}
// y = * ( float * ) &i;
view.setUint32(0, low, true);
view.setUint32(4, high, true);
y = view.getFloat64(0, true);
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration （第一次迭代）
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed（第二次迭代，可以删除）
return y;
}
// 测试用例
// 开方
function sqrtTest() {
for(let i = 1; i < 100000; i++) {
let num = i / 100;
let result = sqrt( num * num );
let rate = (result - num) / num;
rate = Math.abs(rate);
if (rate > 0.002) {
console.warn('sqrt relative error', rate);
}
// console.info('sqrt relative error', rate);
}
}
sqrtTest()
})()
᭄，JS要背锅