g****t
发帖数: 31659 | 1 我记错了,应该是1/sqrt(x)的算法. 2005年Quake III源代码放出来之后传开的.
这个代码,(按wiki上说的),我感觉最神奇的地方:
(1)0x5f3759df怎么来的? 现在还是不清楚.
(2)具体谁写的,不清楚
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 - ... 阅读全帖 |
|
S**I
发帖数: 15689 | 2 ☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:03:00 2011, 美东) 提到:
加recruiter一共6人
4个白男，午饭是一个组的经理 像是 土耳其／印度？ 人
除了最后一个都比较nice
另外每个人有时间都问一遍我RA做的项目，说到想吐
1. java keyword
实现浮点数的平方根，经提醒搞出来了。要考虑小于1的特殊情况； 还要想time
complexity，相对于小数点后精确位数算如何时间复杂度
2. paint fill (toggle)。关键是要考虑space complexity，主要是method stack实时
一共有多少
说了组里的相关一个问题，大概说说TRIE，有一个improvement方法不好答，他说的
用一个计算load balance function，我吐
午饭是其中一个经理，详细讲了下组里的东西，基本和我做的有点相关，感觉他们招人还是很看背景的
3. 给一个数据结构数组，（parent, child）， 重建二叉数，... 阅读全帖 |
|
o***o
发帖数: 11767 | 3 float whatsthefuck (float x){
float y= 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i>>1);
x = *(float*)&i;
x = x*(1.5f - y*x*x);
return x;
} |
|
p*********a
发帖数: 21 | 4 来自主题: JobHunting版 - 算法题求助 这个方法应该是已知的32位计算机上收敛最快的牛顿弦切法. 当然你可以多叠代几次,
不过一两次的叠代精度已经足够用了. 来自以前我在国内经常玩儿的Quake的源代码.
// Magical Square Root Implementation In Quake III
float SquareRootFloat(float number) {
long i;
float x, y;
const float f = 1.5F;
x = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );
y = y * ( f - ( x * y * y ) );
return number * y;
} |
|
g*******y
发帖数: 1930 | 5 来自主题: JobHunting版 - 算法题求助 这个够炫～
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 ); 这句是做什么的？
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) ); “f”是哪里来的?
, |
|
p*********a
发帖数: 21 | 6 来自主题: JobHunting版 - 算法题求助 这段代码当初我是研究了好几天才明白!不过现在回头来看忘的又查不多了.
const float f = 1.5F;
0x5f3759df 是magical number. 其实没什么奇怪的, 但是你要把IEEE的浮点数标准搞
清楚了, 才明白它是怎么来的. 有一篇paper专门讲了一下."Fast Inverse Square
Root", author: Chris Lomont. |
|
z*********8
发帖数: 2070 | 7 为什么不用迭代法呢？
看看游戏Quake里面的算法吧：
float SquareRootFloat(float number) {
long i;
float x, y;
const float f = 1.5F;
x = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );
y = y * ( f - ( x * y * y ) );
return number * y;
} |
|
m*****f
发帖数: 1243 | 8 i = 0x5f3759df - ( i >> 1 );
? |
|
f*******t
发帖数: 7549 | 9 float sqrt( 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 rem... 阅读全帖 |
|
g**e
发帖数: 6127 | 10 重新再学习一下
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
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) )... 阅读全帖 |
|
r*******e
发帖数: 7583 | 11 这个bt的解法依赖于0x5f3759df这个神奇的初值
不是一般的思路能够想到的。。 |
|
h*******e
发帖数: 1377 | 12 还是有点技术含量的。。
float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i >> 1);
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x);
return x;
}
比如这个 就是求 1/sqrt(x) 根号倒数的
当然作者是大学drop out |
|
d*z
发帖数: 150 | 13 这个是如何快速近似计算开方的问题了，实际上本质还是计算开方。
建议googole一下0x5f3759df :) |
|
