1.
牛顿迭代算法
/* 精度控制 */
#define precision 0.0000001
float InvSqrt1(float x)
{
float fDa =1;
float fPre =x;
if(x == 0){
return 0;
}else if(x< 0){
printf("Errorn");
return-1.0;
}
/* 求平方根过程 */
while(fabs(fPre- fDa) > precision){ /*精度控制*/
fPre = fDa;
fDa = (fDa+x / fDa)/(2);
}
/* 返回求平方根之后的数据 */
returnfDa;
}
牛顿迭代算法求平方根的过程也是一个递归过程。
2.卡马克快速平方根算法
卡马克来源的说法:在3D图形编程中,经常要求平方根或平方根的倒数,例如:求向量的长度或将向量归一化。C数学函数库中的sqrt具有理想的精度,但对于3D游戏程式来说速度太慢。我们希望能够在保证足够的精度的同时,进一步提高速度。Carmack在QUAKE3(雷神之锤III )中使用的卡马克快速平方根算法,它第一次在公众场合出现的时候,几乎震住了所有的人。据说该算法其实并不是Carmack发明的,它真正的作者是Nvidia的Gary Tarolli。
float InvSqrt2(float x)
{
float xhalf =0.5f*x;
/* get bitsfor floating VALUE */
inti = *(int*)&x;
/* givesinitial guess y0 */
i= 0x5f375a86 - (i >> 1);
/* convertbits BACK to float */
x= *(float*)&i;
/* Newtonstep, repeating increases accuracy */
x= x*(1.5f - xhalf*x*x);
return1 / x;
}
据说这个算法多年来没人破解,特别是这行代码:i = 0x5f375a86 - (i>> 1)。
对比下牛顿迭代算法、卡马克快速平方根算法和库函数平方根:
int main(int argc, char *argv[])
{
float fa= 101;
structtimeval tv;
while(scanf("%f",&fa)){
/*①,第一次获取时间 */
gettimeofday(&tv,NULL);
printf("time %u:%un", tv.tv_sec, tv.tv_usec);
printf("牛顿迭代 %fn", InvSqrt1(fa));
/*②,第二次获取时间 */
gettimeofday(&tv,NULL);
printf("time %u:%un", tv.tv_sec, tv.tv_usec);
printf("卡马克快速平方根 %fn", InvSqrt2(fa));
/*③,第三次获取时间 */
gettimeofday(&tv,NULL);
printf("time %u:%un", tv.tv_sec, tv.tv_usec);
printf("标准库 %fn", sqrt(fa));
/*④,第四次获取时间*/
gettimeofday(&tv,NULL);
printf("time %u:%un", tv.tv_sec, tv.tv_usec);
}
return0;
}
②-①得到的时间为牛顿迭代算法使用的时间,③-②得到的时间为卡马克快速平方根使用的时间,④-③得到的时间为标准库使用的时间。我们采用两组数据进行测试:
第一组:输入36。
zzq@ubuntu:~/Cprimer/sqrt$ ./sqrt
36
time 1398343935:571032……①
牛顿迭代 6.000000……42
time 1398343935:571074……②
卡马克快速平方根 6.006858……5
time 1398343935:571079……③
标准库 6.000000……5
time 1398343935:571084……④
从这组数据,时间:卡马克快速平方根 = 标准库 < 牛顿迭代;精确度:牛顿迭代 = 标准库 > 卡马克快速平方根。
第二组:输入123456789.987654321
zzq@ubuntu:~/Cprimer/sqrt$ ./sqrt
123456789.987654321
time 1398344737:769933……①
牛顿迭代 11111.111328……1719
time 1398344737:771652……②
卡马克快速平方根 11122.324219……854
time 1398344737:772506……③
标准库 11111.111196……629
time 1398344737:773135……④
笔者加:
微软科学计算器结果:11111.111104999999998874999999381
从这组数据,时间:标准库 < 卡马克快速平方根 < 牛顿迭代;精确度:标准库 > 牛顿迭代 > 卡马克快速平方根。