UDN-企业互联网技术人气社区

板块导航

浏览  : 510
回复  : 1

[其它] 数学之美:平方根倒数速算法中的神奇数字 0x5f3759df②

[复制链接]
白青青的头像 楼主
发表于 2016-9-14 10:52:18 | 显示全部楼层 |阅读模式
  接上篇

  等等,还有更多!

  这个操作的推导告诉你的不只是一个常数的值,你会注意到这个推导不依赖于任何项的具体值,它们只是用于变换的常数,这意味着即使我们改变它们,推导也成立。

  首先,这个计算不关心 L 和 B 具体是什么,它们通过浮点表示给出,这意味着对 64 位和 128 位浮点数可以使用同样的方法,所有要做的只是重新计算常数,这是唯一依赖它们的部分。

  第二,它不关心 σ 的取值,使得对数函数和 x+σ 之间差异最小的 σ 可能不会得到最精确的近似,事实确实如此。这是浮点数的舍入和牛顿法联合造成的,σ 取值本身是一个有趣的课题,McEniry 和 Lomont 有过论述。

  最后,不仅仅只能计算倒平方根,这里指数碰巧是 -1/2,但是对于 -1 到 1 之间的指数,推导依然成立。我们把指数记为 p(因为 e 已经使用),替代掉 -1/2 作同样的推导,得到:
13.jpg

  来试试其他一些指数,首先 p=0.5,普通平方根计算:
12.jpg

11.jpg

  或者代码形式,
  1. 1i = 0x1fbd1df5 + (i >> 1);
复制代码

  同样有效吗?当然:
10.jpg

  这也许是近似计算平方根的一个很著名的方法,但 Google 和维基百科的一个粗略调查显示它并不是。

  甚至对奇数次开方也适用,如立方根
9.jpg

8.jpg

  相应地:
复制代码

  由于这个奇数因子,我们无法使用移位来代替乘法。同样近似很接近:
7.jpg

  这时,你可能会注意到,当指数改变时,我们只需做非常简单的工作:只是通过改变一个线性因子来调整常数值,改变和输入的整形解释相乘的因子。这些操作开销都不大,因此在运行时进行是可行的,而不需要重新计算。如果我们事先对其他两个因子的乘积进行计算:
6.jpg

  则不用提前知道指数,也可计算:
  1. 1i = (1 - p) * 0x3f7a3bea + (p * i);
复制代码

  对项进行整理,还可以减少一步乘法计算:
  1. 1i = 0x3f7a3bea + p * (i - 0x3f7a3bea);
复制代码

  这便是对 -1 到 1 之间任意指数进行快速指数计算的神奇部分,现在我们还差一部分,就是对牛顿近似进行一般化,使得快速指数计算函数对所有指数都适用,且和之前的倒平方根函数一样准确。这部分我没深入,就交给其他博客文章了(很可能是其他人的而不是我)。

  上面表达式包含了一个新的神奇的常数, 0x3f7a3bea。即使它在某种程度上比最初的常数更神奇,最初的常数可由它演变而来,但它依赖于 σ 的主观选取,所以它也不具通用性。把这个常数记为 Cσ ,马上我们会更进一步探究它。

  但首先,我们可以对 p=0 时的公式进行合理性检验。对于 p 取零时,结果应该始终为 1,因为 x0 等于 1,与 x 无关。确实,第二项消失了,因为它乘以了 0 ,我们得到简洁的:
  1. 1i = 0x3f7a3bea;
复制代码

  确实是常数,当解释为浮点值时等于 0.977477,近似为 1,所以合理性检验成立。这也告诉我们一些信息: 当 Cσ 转化为浮点解释时,是一个有意义的值,为 1 或非常接近 1。

  这很有趣,更进一步,Cσ 的整形解释是:
5.jpg

  这很像但不是一个浮点数的形式,唯一的问题是这里是减去而不是加上第二项,这个问题可以很轻易解决:
4.jpg

  现在它看起来像一个浮点数的整形解释,为了具体来看,我们先分辨出指数和尾数,然后计算浮点数值,cσ, 这是指数:
3.jpg

  这是尾数:
2.jpg

  所以常数的浮点数值是:
1.jpg

  确实如果你先用 σ 作除法,0.0450465 除以 2 得 0.02252325,用 1 减去它的 0.97747675 或者刚才的“近似为 1”。这让我们从另一种角度来看待 Cσ,作为一个浮点数的整形解释。用代码计算它:
  1. float sigma = 0.0450465;
  2. float c_sigma = 1 - (0.5f * sigma);
  3. int C_sigma = *(*int)&c_sigma;
复制代码

  注意,对于固定的 σ , 这些皆为常数,编译器应该能够优化整个计算过程。结果为 0x3f7a3beb,不是之前的 0x3f7a3bea ,但只有一字节的不同(最次要的一个字节),这对浮点数计算很正常。要得到最初的常数,本文的标题,只需把结果乘以 1.5。

  我们已经足够深入了,至少我很满足了,没有什么可以继续探究的了。对于我来说,通过这个练习,主要学到的是整形和浮点型之间的位转换操作不是没有意义的,它很怪异但却很经济的数字操作,在计算中很有用。我认为它还有更多有待发现的用处。

相关帖子

发表于 2016-9-14 14:05:47 | 显示全部楼层
赞一个
使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部