删繁就简--快速平方根倒数

lb8820265

删繁就简--快速平方根倒数 [复制链接]

 

   这算是我最佩服的一段代码之一了，效率提高了上十倍，几乎不耗什么内存，而且简单实用。
先上代码：

1. float FastInvSqrt(float x) {
   
2.   float xhalf = 0.5f * x;
   
3.   int i = *(int*)&x;         // evil floating point bit level hacking
   
4.   i = 0x5f3759df - (i >> 1);  // what the fuck?
   
5.   x = *(float*)&i;
   
6.   x = x*(1.5f-(xhalf*x*x));
   
7.   return x;
   
8. }

复制代码

     这段代码可以实现一个数开根号的倒数，而且精度相当的高。通常根号的倒数，比开根号实用。
     用过资源有限型单片机的同学都知道，单片机要计算开方是非常耗时耗内存资源的，我曾经用过MSP430G2553计算一个开根号，结果提示我单片机内存不够，知道开根号有多么恐怖了吧。有了上面的代码，分分钟就搞定了，而且开可以扩展到三角函数中，因为三角函数的简化计算也是由几个开根号的计算来模拟的。
     来看看上面代码的来历吧（下面内容为复制的）：
     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。
最近，QUAKE的开发商ID SOFTWARE遵守GPL协议，公开了QUAKE-III的原代码，让世人有幸目睹Carmack传奇的3D引擎的原码。
     我们知道，越底层的函数，调用越频繁。3D引擎归根到底还是数学运算。
   那么找到最底层的数学运算函数（game/code/q_math.c），必然是精心编写的。里面有很多有趣的函数，很多都令人惊奇，估计我们几年时间都学不完。
     程序中最神奇的就是那个神奇数字 0x5f3759df，实际上整个程序是进行一次牛顿法迭代，有专门的帖子进行分析介绍，作为程序员我们会用就好，相信这代码一定会让你的代码效率提高不少，强迫症者和完美主义者的宝贝哦。

汤权

我表示没看懂代码原理。不过这个代码用起来会很爽，收了！！！

wsmysyn

之前看过，好像有人不信邪，好像找到了另一个数字，不过精度貌似之比这个高了一丢丢，几乎卵用。

EETUX

代码下下来看了下，还有一个不求倒数的
/*
================
SquareRootFloat
================
*/
float SquareRootFloat(float number) {
        long i;
        float x, y;
        const float f = 1.5F;

        x = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;
        i  = 0x5f3759df - ( i >> 1 );
        y  = * ( float * ) &i;
        y  = y * ( f - ( x * y * y ) );
        y  = y * ( f - ( x * y * y ) );
        return number * y;
}

lb8820265

EETUX 发表于 2016-10-14 15:49
代码下下来看了下，还有一个不求倒数的
/*
================
SquareRootFloat
================
*/
...

厉害，我还以为不求倒数就是直接用1除上面算法呢，你补充的看似长了些，优点是没有除法，不知道这个算法会比用1除以上面算法效率高多少

lb8820265

wsmysyn 发表于 2016-10-14 12:24
之前看过，好像有人不信邪，好像找到了另一个数字，不过精度貌似之比这个高了一丢丢，几乎卵用。

是的，不知道原作者是怎么得出来的，真心佩服

白丁

https://bbs.eeworld.com.cn/forum ... =arm%2B%BC%C6%CA%FD
看看这个帖子里的0x49249249和0xc71c71c7是怎么实现的啊

lb8820265

白丁 发表于 2016-10-14 19:18
https://bbs.eeworld.com.cn/forum.php?mod=viewthread&tid=459539&highlight=arm%2B%BC%C6%CA%FD
看看这个 ...

不错，你这个代码确实有点意思，应该也就是分组分别计算的意思，汇编代码确实是相当简洁，不过改成C语言效率貌似就低了很多，我知道一个快速方法，在C语言下效率还是挺高的：
int BitCount(unsigned int n)
{
    unsigned int c =0 ;
    for (c =0; n; ++c)
    {
        n &= (n -1) ; // 清除最低位的1
    }
    return c ;
}

xuyiyi

lb8820265 发表于 2016-10-15 00:24
不错，你这个代码确实有点意思，应该也就是分组分别计算的意思，汇编代码确实是相当简洁，不过改成C语言 ...

这个方法确实不错，只是在 1 的个数越多，效率越低。

ywlzh

http://mp.weixin.qq.com/s?__biz= ... 5a3f61e1&scene=0#rd


就没人发现这个吗？这么好的解释！

lb8820265

ywlzh 发表于 2016-10-16 18:43
http://mp.weixin.qq.com/s?__biz=MzAxNDI5NzEzNg==&mid=2651157212&idx=1&sn=9f67da1a6dd4c182bf8b8e5c98b ...

哈哈，这个帖子我也看了，确实是大牛啊