卡马克算法 开方函数 哪位解释一下

scutan

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

1. 
   
2. double sqrt2(double y)
   
3. {
   
4.         double x = (double)(rsqrt((float)y));
   
5.         double z = y * 0.5;
   
6.         x = 1.5 * x - (x * x * x * z);
   
7.         x = 1.5 * x - (x * x * x * z);
   
8.         x = 1.5 * x - (x * x * x * z);
   
9.         return x * y;
   
10. }
    

复制代码

anders0913

哪里摘来的？quake3里面得么？~~

sharkphoon

tjj bdq
ding!

cugb_cat

http://www.cnblogs.com/vagerent/archive/2007/06/25/794695.html
这篇里的不知道是不是你想要的。

anders0913

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

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

1. 
   
2. //
   
3. // Carmack在QUAKE3中使用的计算平方根的函数
   
4. //
   
5. float CarmSqrt(float x){
   
6.     union{
   
7.         int intPart;
   
8.         float floatPart;
   
9.     } convertor;
   
10. 
    
11.     union{
    
12.         int intPart;
    
13.         float floatPart;
    
14.     } convertor2;
    
15. 
    
16.     convertor.floatPart = x;
    
17.     convertor2.floatPart = x;
    
18.     convertor.intPart = 0x1FBCF800 + (convertor.intPart >> 1);
    
19.     convertor2.intPart = 0x5f3759df - (convertor2.intPart >> 1);
    
20.     return 0.5f*(convertor.floatPart + (x * convertor2.floatPart));
    
21. }
    

复制代码

anders0913

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

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


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

呵呵，赞~~

anders0913

http://en.wikipedia.org/wiki/Fast_inverse_square_root

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

cugb_cat

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

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


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

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

scutan

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

嗯。就是里面得到的。