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

夕阳与月

原帖由 gunmanmax 于 2010-10-11 16:39 发表
呵呵,毕业设计搞的是quake1 引擎的portal算法,还没接触过quake3引擎
不过卡马克给出的那个数字真的是很有意思,难道数学真的是越复杂越明了吗?
我们这种还挣扎在微积分离散数学的人是无法理解的啊 ...

逼近理论大部分结论的原理都是Taylor展开啊，只是小部分需要一点代数和泛函知识。有微积分的知识基本足够了

=origin=

现在早不打quake3了，改打ql了，据说ql的网络代码优化得更棒！
国内打ql的基本都集中在这里：
http://bbs.wasdcn.com/

cpw3yac7

天书，又见天书

疯子太

又是论文帝？？

王潇

微积分挂科的飘过

loend

[害怕] 高数常年崩溃的人~~~~~~~~

FLZ012

我表示我只管用 不管这几个函数是怎么实现的………………………………………………

brien

那篇Purdue大学的论文很有意思，学习算法和加密的时候曾经拜读过，这个数字0x5f3759df也很神奇，效率和精度都很完美。

icame

好帖子 看回帖就能看出来人受的教育程度  数值方法是工科学生研究生必修的    基础好点的本科也能会  学计算机的更不用说了

[ 本帖最后由 icame 于 2010-10-11 20:06 编辑 ]

keith9

-----Original Message-----
From: John Carmack
Sent: 26 April 2004 19:51
Subject: Re: Origin of fast approximated inverse square root

At 06:38 PM 4/26/2004 +0100, you wrote:

>Hi John,
>
>There's a discussion on Beyond3D.com's forums about who the author of
>the following is:
>
>float InvSqrt (float x){
>    float xhalf = 0.5f*x;
>    int i = *(int*)&x;
>    i = 0x5f3759df - (i>>1);
>    x = *(float*)&i;
>    x = x*(1.5f - xhalf*x*x);
>    return x;
>}
>
>Is that something we can attribute to you? Analysis shows it to be
>extremely clever in its method and supposedly from the Q3 source.
>Most people say it's your work, a few say it's Michael Abrash's. Do
>you know who's responsible, possibly with a history of sorts?

Not me, and I don't think it is Michael. Terje Matheson perhaps?

John Carmack

keith9

-----Original Message-----
From: Terje Mathisen
Sent: 22 August 2005 07:49
Subject: Re: FW: Origin of fast approximated inverse square root

ryszard wrote:

> Hey Terje,
>
> This question has come up again since id released the source to Quake
> 3 Arena.
> > Are you the guy who wrote that fast implementation of inverse square root?
> If so, do you have a history of where it came from and how you came up
> with it? A whole bunch of hackers and geeks would love to know and
> since John says it wasn't him or likely Michael, was it you?

Hello Ryszard, and hello again John, it's been a few years since we last met. :-(

Thanks for giving me as a possible author, when I first saw the subject I did
indeed think it was some of my code that had been used. :-)

I wrote a very fast (pipelineable) & accurate invsqrt() 5+ years ago, to help
a Swede with a computational fluid chemistry problem.

His simulation runs used to take about a week on either Alpha or x86 systems,
with my modifications they ran in half the time, while delivering the exact
same final printed results (8-10 significant digits).

The code shown below is not the same as what I wrote, I would guess it mostly
stays within a fraction of a percent? The swede needed at least 48 sigificant
bits in his results, so I employed a much more straightforward table lookup
plus NR-iteration. Since water molecules contain three atoms it was quite
straightforward to calculate three such invsqrt() values in parallel, this was
enough to avoid almost all bubbles in the fp pipelines.

I do think I recognize the style of the Q3A code however, it looks a lot like
something you'll find in the old HAKMEM documents from MIT. :-)

Regards,

Terje

louyudewan

很强大，膜拜下先                                

keith9

-----Original Message-----
From: Gary Tarolli
Sent: Mon 05/09/2005 14:23
Subject: RE: FW: Origin of fast approximated inverse square root

A blast from the past!
I definitely recognize the code below, but I can't take credit for it.
I remember running across it over 10 years ago, and I also remember
rederiving it. I think it's just Newton-Raphson iteration with a very
clever first approx.

I also remember simulating different values for the hex constant
0x5f3759df. I may have done this for the IRIS indigo work I did,
or some consulting at Kubota, I'm not 100% sure.

Given the amount of math it does, and its accuracy, and not requiring
a table, it is a pretty great piece of code.

I especially like the integer ops
   i = 0x5f3759df - (i >> 1);
which actually is doing a floating point computation in integer - it
took a long time to figure out how and why this works, and I can't
remember the details anymore.

Ah those were the days - fast integer and slow floating point....

So it did pass by my keyboard many many years ago, I may have tweaked
the hex constant a bit or so, but other than that I can't take credit
for it, except that I used it a lot and probably contributed to its
popularity and longevity.

p.s. sorry in taking so long to reply

结论，这个算法是Gary Tarolli和他在SGI的同事于2001年左右发明的。

chenyiheng

天啊！值得膜拜，看了个大概懂，重新读一下看看。。牛牛迭代法算是见识过了。。卡马克的这个值绝对是神来之笔！！

elenewton

卡神就缺一个罗梅洛做设计。要是DOOM3当年有神人设计一下关卡，就不会被半条命2比下去了。

zy831127

当年高一数学期中考试全班平均分37

chenyiheng

悲剧的是，我拿VC6.0试验了一下，为毛计算精度有点低啊。。。。

乌鸦z

原帖由 FLZ012 于 2010-10-11 19:16 发表
我表示我只管用 不管这几个函数是怎么实现的………………………………………………

用的结果就是看起来差不多的画面效果,卡神的只需要9600GT就流畅了,某游戏最少需要GT460才稳定60FPS

长腿大侠

原帖由 icame 于 2010-10-11 20:04 发表
好帖子 看回帖就能看出来人受的教育程度  数值方法是工科学生研究生必修的    基础好点的本科也能会  学计算机的更不用说了

本科和学计算机的也不见得会，原因是多方面的，比如有的上学的时候就是混的、有的毕业以后不从事本专业及其相关行业的。。。。。。。。。。。。基本上就都忘的差不多了

ytj

原帖由 chenyiheng 于 2010-10-12 07:14 发表
悲剧的是，我拿VC6.0试验了一下，为毛计算精度有点低啊。。。。

反正是求一个向量正交化，0.1%的精度足够用。
你以为精确到小数点后一长串有意义么