Mar 31

LeetCode 69 - x 的平方根 不指定

felix021 @ 2019-3-31 15:34 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(255) | Via 本站原创 | |
这是罗凯同学布置的 Golang 学习作业。

这题之前用 Python 刷过,用的是二分法,在 [1, n / 2] 区间内,找到第一个 x,使得 x ^ 2 <= n < (x + 1) ^ 2 ,用的是 STL 中 lowerbound 的算法。

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            raise Exception("invalid input")
        if x < 2:
            return x
       
        left = 1
        length = x / 2
        while length > 1:
            half = length / 2
            middle = left + half
            if middle * middle > x:
                length = half
            else:
                left = middle
                length = length - half
        return left


罗凯同学提到,应该使用牛顿迭代法来完成。这个方法是听说过的,但是早就忘了,于是到 wikipedia 去找了一下:

https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95

求函数 f(x) 的零点,可以通过选取曲线上的任意一个点 x0 开始,然后计算 x1 = x0 - f(x1) / f'(x1) 的方式迭代,通常得到一个比 x0 更接近零点的 x1 。通过不断迭代,最终我们能找到一个零点 xn 。

对于求平方根,我们是要找到一个 x,使得 x ^2 - n = 0,也就是这里的 f(x) = x ^ 2 - n, f'(x) = 2 * x (勉强还记得这个求导公式……)

有了这个,答案就呼之欲出了:

import "math"

func mySqrt(x int) int {
    f := func (i float64) float64 {
        return i * i - float64(x)
    }
    g := func (i float64) float64 {
        return 2 * i
    }
    var i float64 = 1.0
    for math.Abs(f(i)) > 1e-6 {
        i = i - f(i) / g(i)
    }
    return int(math.Floor(i))
}


做完以后,我想起 Quake III 的作者 John Carmack 的 平方根倒数速算法,摘录一段内容:( src: https://blog.csdn.net/zyex1108/article/details/53540824 )

引用

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


这个平方根倒数算法正是其中的一个例子。在3D游戏引擎中,求取照明和投影的波动角度与反射效果时,常需计算平方根倒数,而求平方根的常用算法效率较低。


Carmack 通过使用一个惊为天人的魔术常量 0x5f3759df,只需要做 1 次迭代(Quaker III源码中的为了提高精度的第二次迭代被注视掉了),就能得到一个足够精度的平方根,大幅提高了 3D 引擎的运行效率。

关于这个魔术常量,Carmack 表示并不是他自己发明的,至今为止仍未能确切知晓算法中所使用的特殊常数的起源。但 Carmack 凭一己之力,撑起了一个 3D 引擎的时代,以至于在1999年,登上了美国时代杂志评选出来的科技领域50大影响力人物榜单,并且名列第10位。

感兴趣的同学,可以在 Wikipedia 的 平方根倒数速算法 了解更多细节:

https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95

转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: http://www.felix021.com/blog/feed.php
repostone Email Homepage
2019-4-21 16:12
都是技术。
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]