init-qy的个人博客
0%

发表于 更新于 分类于
本文字数： 2.1k 阅读时长 ≈ 3 分钟

在机缘巧合下，了解到了这么一个神奇的16进制数字0x5f3759df，顺便记录一下

科学改变世界，数学改变科学

上回遇到的不讲道理的数字是0.75，它出现在Java HashMap的源码中，含义是默认的负载因子。简单介绍一下这个值的含义：在HashMap中达到容量的0.75倍时（即容量为16时元素为12时）会对HashMap进行扩容，扩容的意义在于减少hash冲突，避免HashMap退化为链表而大大增加查询时间。至于这个值为什么是0.75，有个很简单的解释：提高空间利用率和减少查询成本的折中，主要是泊松分布，0.75的话碰撞最小

好吧，这个解释我能接受，这个0.75也能接受，但是我完全无法想象0x5f3759df这个玩意儿是怎么得来的完全想象不出来。
以下是关于这个魔法数的背景和源码介绍，部分引用自知乎：0x5f3759df这个快速开方中的常数的数学依据是什么？，及另一篇博客：0x5f3759df的数学原理；中文版可以看这个：数学之美：平方根倒数速算法中的神奇数字 0x5f3759df

Quake-III Arena (雷神之锤3)是90年代的经典游戏之一。

该系列的游戏不但画面和内容不错，而且即使计算机配置低，也能极其流畅地运行。这要归功于它3D引擎的开发者约翰-卡马克（John Carmack）。事实上早在90年代初DOS时代，只要能在PC上搞个小动画都能让人惊叹一番的时候，John Carmack就推出了石破天惊的Castle Wolfstein, 然后再接再励，doom, doomII, Quake…每次都把3-D技术推到极致。他的3D引擎代码资极度高效，几乎是在压榨PC机的每条运算指令。当初MS的Direct3D也得听取他的意见，修改了不少API。

这个神奇的数字出现在这个3D引擎的底层代码中，它的作用是将一个数开平方并取倒数，经测试这段代码比(float)(1.0/sqrt(x))快4倍：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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) ); // bk010122 - FPE?
#endif
#endif
    return y;
}
关于迭代法

迭代法通过旧值计算新值，循环往复，非常符合计算机语言。
最经典的迭代算法是欧几里德算法（辗转相除法），用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：

gcd(a,b) = gcd(b,a mod b)

除此之外，常见的比如斐波那契数列，也可以用迭代法计算。一般来说，递归算法拥有很好的可读性，但往往需要更多的开销，这时可以将递归转换为递推（迭代），以期更高的效率。这一点我在做算法题时深有感触。

关于牛顿迭代法

简介：牛顿迭代法-百度百科
300年前的思想到现在仍然可以发光发热，数学果然是文明的基石
一般sqrt算法就是使用牛顿迭代法,用x-f(x)/f'(x)来不断的逼近f(x)=a的根。

简单来说比如求平方根,f(x)=x^2=a ,f'(x)= 2*x,f(x)/f'(x)=x/2,把f(x)代入x-f(x)/f'(x)后有(x+a/x)/2，现在我们选 a=5 ,选一个猜测值比如2，那么我们可以这么算

  1. 5/2 = 2.5；(2.5+2)/2 = 2.25；

  2. 5/2.25 = 2.22;(2.25+2.22)/2 = 2.235；

  3. 5/2.235 = 2.23713;(2.235+2.23713)/2 = 2.236065；

仅仅三步我们得到的值就和sqrt(5)= 2.23606797相差无几，可以预见，如此反复迭代其结果收敛于sqrt(5)。一般可以迭代4~7次后就能得到一个相对精确的值。这是建立在猜测值相对不精确来说的，理论上，只要猜测值足够精确，就可以大幅压缩迭代次数，于是这个数0x5f3759df出现了。

具体的推导过程可以参考以上的博客，这边引用一下文末的结论，这同时激起我对游戏引擎的好奇。

如此神奇，如此怪异，如此不符合常理，如此符合常理，如此美丽。

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

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 2 分钟

2020-10

  1. 钉钉不支持   text标签中的空格用中文全角空格代替{{'　'}}
  2. 钉钉 dd.switchTab 方法有问题,既不报错也无提示,现解决方案由 dd.reLaunch 代替
  3. 钉钉(与支付宝,未测试) <swiper>组件下只能接<swiper-item>组件,使用view包裹<swiper-item>组件可能无法正常显示

    swiper组件使用样例

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    <swiper :indicator-dots="{{indicatorDots}}"
            :autoplay="{{autoplay}}"
            :interval="{{interval}}"
            :duration="{{duration}}"
            :circular="{{circular}}"
            style="height:auto">
      <swiper-item a:for="{{banners}}">
        <view onTap="goToPage" class="banner">
          <image src="{{item.picUrl||'http://mallplus.oss-cn-hangzhou.aliyuncs.com/test/20190813/G0001/05120000001/f59b57016e5847de8c0fd283253b926f.jpg'}}" mode="widthFix" class="banner-image"/>
        </view>
      </swiper-item>
    </swiper>

    选项组件m-picker

  • 使用setColumnValues实现多项联动效果,具体参照 brand-add.js
  • onConfirm中 detail.value 为选项index数组 detail.detail 为选项值数组

2020-11

1.非常重要 不要在data初始化的时候调用函数进行赋值,否则页面会找不到

反例

1
2
3
data:{
   a:getProjectName()
}

正例

1
2
3
4
5
6
7
8
data:{
    a:''
}
onLoad() {
    this.setData({
      a:getProjectName()
    })
}

发表于 更新于
本文字数： 20 阅读时长 ≈ 1 分钟

和Hexo相关的学习文档会归集在这个页面