Chinaunix

标题: 卡马克算法开方函数哪位解释一下 [打印本页]

作者: scutan 时间: 2009-07-13 17:03
标题: 卡马克算法开方函数哪位解释一下
看到一个快速开方算法，称为卡马克算法，是在精度不高的sqrt()函数之上进行了封装，得到一个精度更高的开方函数。如下所示，rsqrt()为sqrt()函数的倒数，输入输出都为float类型。最终的结果为double的精度。我测试了一下，确实精度很高，但是不太懂原理，哪位给讲讲，谢谢。

double sqrt2(double y)
{
double x = (double)(rsqrt((float)y));
double z = y * 0.5;
x = 1.5 * x - (x * x * x * z);
x = 1.5 * x - (x * x * x * z);
x = 1.5 * x - (x * x * x * z);
return x * y;
}

复制代码

作者: xiaomiao 时间: 2009-07-13 17:03
提示: 作者被禁止或删除内容自动屏蔽

作者: anders0913 时间: 2009-07-13 17:10
哪里摘来的？quake3里面得么？~~

作者: sharkphoon 时间: 2009-07-13 17:16
tjj bdq
ding!

作者: cugb_cat 时间: 2009-07-13 17:17
http://www.cnblogs.com/vagerent/archive/2007/06/25/794695.html
这篇里的不知道是不是你想要的。

作者: anders0913 时间: 2009-07-13 17:24

原帖由 cugb_cat 于 2009-7-13 17:17 发表
 http://www.cnblogs.com/vagerent/archive/2007/06/25/794695.html
这篇里的不知道是不是你想要的。

那篇文章里面说的和lz的算法不大一样~~

//
// Carmack在QUAKE3中使用的计算平方根的函数
//
float CarmSqrt(float x){
union{
int intPart;
float floatPart;
} convertor;
union{
int intPart;
float floatPart;
} convertor2;
convertor.floatPart = x;
convertor2.floatPart = x;
convertor.intPart = 0x1FBCF800 + (convertor.intPart >> 1);
convertor2.intPart = 0x5f3759df - (convertor2.intPart >> 1);
return 0.5f*(convertor.floatPart + (x * convertor2.floatPart));
}

复制代码

作者: anders0913 时间: 2009-07-13 17:36

原帖由 xiaomiao 于 2009-7-13 17:31 发表
ohn Carmack的密码：0x5f3759df

有人在Quake III的源代码里面发现这么一段用来求平方根的代码:

/*================SquareRootFloat================*/
float SquareRootFloat(float number)
{
lo ...

呵呵，赞~~

作者: anders0913 时间: 2009-07-13 17:43
http://en.wikipedia.org/wiki/Fast_inverse_square_root

Lomont为此写下一篇论文，"Fast Inverse Square Root"。

作者: cugb_cat 时间: 2009-07-13 18:03

原帖由 xiaomiao 于 2009-7-13 17:31 发表
ohn Carmack的密码：0x5f3759df

有人在Quake III的源代码里面发现这么一段用来求平方根的代码:

/*================SquareRootFloat================*/
float SquareRootFloat(float number)
{
lo ...

卡马克不会也是一个数字一个数字的试出来的吧？

作者: scutan 时间: 2009-07-13 18:03

原帖由 anders0913 于 2009-7-13 17:10 发表
哪里摘来的？quake3里面得么？~~

嗯。就是里面得到的。

作者: scutan 时间: 2009-07-13 18:06

原帖由 xiaomiao 于 2009-7-13 17:31 发表
ohn Carmack的密码：0x5f3759df

有人在Quake III的源代码里面发现这么一段用来求平方根的代码:

/*================SquareRootFloat================*/
float SquareRootFloat(float number)
{
lo ...

谢谢，你给的资料很有用。
不过1楼的代码中没有这个0x5f3759df的神秘数字，那个代码是怎么搞出来的呢？

作者: scutan 时间: 2009-07-13 18:09

原帖由 xiaomiao 于 2009-7-13 17:31 发表
ohn Carmack的密码：0x5f3759df

有人在Quake III的源代码里面发现这么一段用来求平方根的代码:

/*================SquareRootFloat================*/
float SquareRootFloat(float number)
{
lo ...

谢谢，我再看看，消化一下。

作者: xhl 时间: 2009-07-13 18:33

原帖由 xiaomiao 于 2009-7-13 17:31 发表
ohn Carmack的密码：0x5f3759df

有人在Quake III的源代码里面发现这么一段用来求平方根的代码:

/*================SquareRootFloat================*/
float SquareRootFloat(float number)
{
lo ...

有人测试过吗？

我知道quake 的作者是神，不是人。但都21世纪了，怎么还搞盲目崇拜呢。

但这段代码，我曾经测试了几次，都觉得没系统提供的sqrt 精确跟快。（windows / freebsd）

也许是我没体会到其中的真谛把。呵呵。

作者: scutan 时间: 2009-07-13 18:46
明白了。
sqrt(x) = x * (1 / sqrt(x)).
我在1楼给的代码就是在对(1 / sqrt(x))的精度不断进行提升，使得最终的精度更高。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)