Quake-III代码里神奇的浮点开方函数

Quake-III

Arena

(

雷神之锤

3)

是

90< /p>

年代的经典游戏之一。

该系列的游戏不但画

面和内容不错，而且即使计算机配置低，也能极其流畅地运行。这要归功于它

3

D

引擎的开发者约翰

-

卡马克（

John

Carmack

）。事实上早在

90

年代初

DOS

时

代，只要能在

PC

上搞个小动画都能让人惊叹一番的时候，

John

Carm ack

就推

出了石破天惊的

Castl e

Wolfstein,

然后再接再励，

doom,

doomII,

Quake...

每

次都把

3-D

技术推到极致。他的

3D

引擎代码资极度高效，几乎是在压榨

P C

机

的每条运算指令。当初

MS

的

Direct3D

也得听取他的意见，修改 了不少

API

。

最近，

QUAKE

的开发商

ID

SOFTWARE

遵守

GPL

协议，公开了

QUAKE-III

Carmack

传奇的

3D

引擎的原码。

这是

QUAKE- III

原代码的下载地址：

/file.x?fid=7547

(

下面是官方的下载网址，

搜索

“quake3

-1.32b-

”

可以找到一大堆中文

网页的

ftp:///idstuff/source/

)

我们知道，越底层的函数，调 用越频繁。

3D

引擎归根到底还是数学运算。那

么找到最底层的数学运算函数（在

game/code/q_math.c

），

必然是精心编写

的。里面有很多有趣的函数，很多都令人惊奇，估计我们几年时间都学不完。

在

game/code/q_math.c

里发现了这样一段代码。

它的作用是将一个数开平方并

取倒，经 测试这段代码比

(float)(1.0/sqrt(x))

快

4

倍：

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

re

moved

#ifndef

Q3_VM

#ifdef

__linux__

assert(

!isnan(y)

);

//

bk010122

-

FPE?

#endif

#endif

return

y;

}

函数返回

1/sqrt(x)

，这个函数在图像处理中比

sqrt(x)

更有用。

注意到这个函 数只用了一次叠代！（其实就是根本没用叠代，直接运算）。

编译，实验，这个函数不仅 工作的很好，而且比标准的

sqrt()

函数快

4

倍！要知

道，编译器自带的函数，可是经过严格仔细 的汇编优化的啊！

这个简洁的函数，最核心，也是最让人费解的，就是标注了

“

what

the

fuck?”

的一句

i

=

0x5f3759df

-

(

i

>>

1

);

再加上

y

=

y

*

(

threehalfs

-

(

x2

*

y

*

y

)

);

两句话就完成了开方运算！而且注意到，核心那句是定点 移位运算，速度极快！

特别在很多没有乘法指令的

RISC

结构

CPU

上，这样做是极其高效的。

算法的原理其实不复杂

,

就是牛顿迭代法

,

用

x-f( x)/f'(x)

来不断的逼近

f(x)=a

< br>的

根。

简单来说比如求平方根

,f(x)=x^2=a

,f'(x)=

2*x,f(x)/f'(x)=x/2,< /p>

把

f(x)

代入

x-f(x)/f'(x)

后有

(x+a/x)/2

，现在我们选

a=5,

选一个猜测值比如

2

，

那么我们可以这么算

5/2

=

2.5;

(2.5+2)/2

=

2.25;

5/2.25

=

xxx;

(2.25+xx

x)/2

=

xxxx ...

这样反复迭代 下去，结果必定收敛于

sqrt(5)

，没错，一般的求

平方根都是这么算的但是卡马克

(quake3

作者

)

真正牛

B

的地方是他选择了一个

神秘的常数

0x5f3759df

来计算那个猜测值就是我们加注释的那一行

,

< br>那一行算

出的值非常接近

1/sqrt(n),