欢迎光临
我们一直在努力

0x5f375a86传奇算法-求平方根倒数

0x5f375a86来自一个传奇算法(求平方根倒数),此算法最早被认为是由约翰·卡马克所发明(发明时这个值为0x5f3759df,后来由Lomont通过暴力穷举找到这个更优值),但后来的调查显示,该算法在这之前就于计算机图形学的硬件与软件领域有所应用,如SGI和3dfx就曾在产品中应用此算法。


float xsqrt( float v )
{
  static int i ;
  static float x2, y ;
  static const float threehalfs = 1.5f ;
  
  x2 = v * 0.5f ;
  y  = v ;
  i  = * ( int * ) &y ;
  i  = 0x5f375a86 - ( i >> 1 ) ;
  y  = * ( float * ) &i ;
  y  = y * ( threehalfs - ( x2 * y * y ) ) ;
  y  = y * ( threehalfs - ( x2 * y * y ) ) ;
  return v * y ;
}

float Q_sqrt(float z)
{
	unsigned int b;
	float g;
	b = *(unsigned int *) &z;

	b = (b >> 1) + 0x1fbffb72;  //wtf
	g = *(float *) &b;
	g = (.5 * g + .5 * z / g);
	g = (.5 * g + .5 * z / g);
	return g;
}

由来

就现在所知,此算法最早由Gary Tarolli在SGI Indigo的开发中使用。虽说随后的相关研究也提出了一些可能的来源,但至今为止仍未能确切知晓此常数的起源。
这个引擎的源代码里包括一个反平方倒数的算法,其速度要比标准的牛顿迭代法快上 4 倍,而其中的关键是一行神秘的代码和一个莫名其妙的数字:[ i = 0x5f3759df – ( i >> 1 ); // what the fuck? ] 。没有人知道Carmack是怎么发现这个数字的。普度大学的数学家Lomont觉得很好玩,决定要研究一下卡马克弄出来的这个猜测值有什么奥秘。Lomont也是个牛人,在精心研究之后从理论上也推导出一个最佳猜测值,和卡马克的数字非常接近, 0x5f37642f。卡马克真牛,他是外星人吗?
传奇并没有在这里结束。Lomont计算出结果以后非常满意,于是拿自己计算出的起始值和卡马克的神秘数字做比赛,看看谁的数字能够更快更精确的求得平方根。结果是卡马克赢了… 谁也不知道卡马克是怎么找到这个数字的。最后Lomont怒了,采用暴力方法一个数字一个数字试过来,终于找到一个比卡马克数字要好上那么一丁点的数字,虽然实际上这两个数字所产生的结果非常近似,这个暴力得出的数字是0x5f375a86。
Lomont为此写下一篇论文,”Fast Inverse Square Root”。
赞(3) 打赏
未经允许不得转载:huangea的博客 » 0x5f375a86传奇算法-求平方根倒数

评论 7

  1. #1

    一个博客能让人流连忘返,讲真,靠的是实力!

    zhixie7年前 (2018-05-12)回复
  2. #2

    I really can’t believe how great this site is. Keep up the good work. I’m going to tell all my friends about this place.

    Georgie Digmann7年前 (2018-05-26)回复
  3. #3

    让人百看不厌的博客,真的不是很多!

    巨根增大网7年前 (2018-06-01)回复
  4. #4

    这个博客就像一座宝藏,我是来掘金滴!

    藏金网7年前 (2018-06-07)回复
  5. #5

    第一次看,感觉还挺新鲜!

    kitty237年前 (2018-06-18)回复
  6. #6

    炎热夏天,闲来无事,拜读博客,消暑解闷!

    9487年前 (2018-06-22)回复
  7. #7

    从百度点进来的,学习学习,呵呵!

    爱就爱啦7年前 (2018-07-03)回复

有趣的网站

支持快讯、专题、百度收录推送、人机验证、多级分类筛选器,适用于垂直站点、科技博客、个人站,扁平化设计、简洁白色、超多功能配置、会员中心、直达链接、文章图片弹窗、自动缩略图等...

联系我们联系我们

觉得文章有用就打赏一下文章作者

非常感谢你的打赏,我们将继续给力更多优质内容,让我们一起创建更加美好的网络世界!

支付宝扫一扫打赏

微信扫一扫打赏

登录

找回密码

注册