• 欢迎访问交通人网站!
  • 分享一款小游戏:信任的进化
  •    发表于5年前 (2017-10-10)  模型与算法 |   抢沙发  1999 
    文章评分 2 次,平均分 5.0

    在编程开发中,经常需要去计算一个数的平方根,小编一般是直接调用系统函数 Math.Sqrt()

    当然除了系统函数,我们也可以自己编写函数进行求解,常用的方法有二分法和牛顿迭代法。

    二分法

    一种神奇的 Sqrt 函数实现方法
    二分法

    二分法的基本思想:对于区间 \([m,n]\) 上连续不断且 \(f(m)·f(n) < 0\) 的函数 \(y=f(x)\),通过不断地把函数 \(f(x)\) 的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值。

    显然,\(\sqrt{a}\) 是函数 \( f(x) =x^2 - a\) 的一个零点,但需要注意的是,如果直接将区间初始化为 \([0,a]\) 是无法保证 \( f(0)·f(a) = a^2 (1-a) < 0 \) 恒成立的。因为当 \( a < 1\) 时,\(f(x)\) 的正实根位于区间 \([0,a]\) 之外,此时需要将区间上限扩大为大于 1 的值。

    牛顿迭代法

    牛顿迭代法的基本思想:以曲线的切线与 \(x\) 轴的交点逼近曲线的零点。

    具体来说:对于函数 \( f(x)\),选取一个初始值 \(x_0\),过点 \((x,f(x_0))\) 作曲线 \( f(x)\) 的切线 \(L_1\),其方程为 \( y= f(x_0) + f'(x_0)(x-x_0)\),计算切线 \(L_1\) 与 \(x\) 轴交点的横坐标 \(x_1=x_0 - \frac{f(x_0)}{f'(x_0)}\) 作为 \( f(x) = 0\) 根的近似值,然后过点 \((x,f(x_1))\) 再作曲线 \( f(x)\) 的切线 \(L_2\),其方程为 \( y= f(x_1) + f'(x_1)(x-x_1)\),计算切线 \(L_2\) 与 \(x\) 轴交点的横坐标 \(x_2=x_1 - \frac{f(x_1)}{f'(x_1)}\) 作为 \( f(x) = 0\) 根的近似值。重复以上过程,直至满足精度要求。

    一种神奇的 Sqrt 函数实现方法
    牛顿迭代法

    对于函数 \( f(x) =x^2 - a\),有 \( f'(x) =2x\),因此近似根的迭代公式为: \[x_{n+1}=x_{n} - \frac{f(x_{n})}{f'(x_{n})} = =x_{n} - \frac{x^2_{n}-a}{2x_{n}} = \frac{1}{2}(x_n + \frac{a}{x_n})\]

    不过从运行效率上来看,似乎并没有自己编写函数的需求,因为系统函数的运行效率明显优于以上两个自编函数。

    直到某一天,小编在网络上看到一个神奇的方法,心中万马奔腾,如同代码中注释一样 :“what the fuck?”

    这段代码来自于 90 年代的经典游戏之一 Quake-III Arena(雷神之锤 3),它的作用是将一个数开平方并取倒数。

    有网友测试发现,这段代码竟然比 (float)(1.0/sqrt(x)) 快 4 倍!

    毋庸置疑的“神奇”!

    至于卡马克(雷神之锤 3 的作者)是怎么发现这个奇妙的数字的,我们不得而知。

    不过,普渡大学的数学家 Chris Lomont 看到这个问题后曾有一些研究,他从理论上推导出一个最佳猜测值:0x5f37642f,和卡马克的数字非常接近,但是计算精度和速度不及卡马克的数字。面对这样的而结果,Chris Lomont 很受伤,不过好在通过暴力试算,总算找到了一个比卡马克的数字要好上那么一丁点的数字:0x5f375a86,虽然实际上这两个数字所产生的结果非常近似。

    从 Chris Lomont 的分析来看,这个神奇的方法是巧妙利用了单精度浮点数的相关特性。

    我们知道,单精度浮点数占用 4 个字节(32 位)存储空间,具体由符号位(1 位),阶码(8 位)和尾数(23 位)构成。以下图为例,符号位为 \(s=0\),阶码 \(E=124\),尾数 \(M=2097152\),对应的数字为:\[x=(-1)^s(1+\frac{M}{2^{23}})2^{E-127} =(-1)^0(1+0.25)2^{-3}\]

    一种神奇的 Sqrt 函数实现方法
    单浮点数

    鉴于以上原因,在 C# 中实现该神奇算法时,不能像其他算法一样将 float 改写为 double,同时还必须使用 unsafe 关键字。

    以下是基于神奇算法的求平方根函数(C#):

    对于神奇数字,感兴趣的朋友可以到文后下载 Chris Lomont 的论文《FAST INVERSE SQUARE ROOT》,或者到这里寻找答案。

    打赏
    微信
    支付宝
    微信二维码图片

    微信 扫描二维码打赏

    支付宝二维码图片

    支付宝 扫描二维码打赏

    相关下载

     

    除特别注明外,本站所有文章均为交通人原创,转载请注明出处来自http://www.hijtr.com/fast-sqrt/

    交通人博客是交通人工作室(JTR Studio)建立的交通人系列网站之一,是交通人工作室的主阵地,旨在整合和分享交通行业相关资讯,具体包括但不限于行业新闻、行业动态,以及行业相关规范、书籍、报告和软件等资源。

    发表评论

    表情 格式

    *

    暂无评论

    
    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享