开根号算法

  cheney

    这是Quake-III Arena (雷神之锤3)里的代码改过来的,之前在大神Matrix67的博客里看到过,但是一直没有亲自实现。最近需要在一个嵌入式系统里开根号,想起这个代码,拿出来。

    首先在PC机下尝试,一个是调用库函数的 sqrt(),一个是我看的那篇文章给的参考函数SquareRootFloat(),我在此基础上又做了一些修改 CoolSqrt()(为嵌入式做准备)。以下是函数即测试代码,各运行一百万次开方:

    	/* 开方函数测试
    	 ChanneW
    	 C-Free
    	 2012年09月13日
    	*/
    	
    	#include <stdio.h>
    	#include <math.h>
    	#include <time.h>
    	
    	float CoolSqrt (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 (1/x);
    	}
    	
    	float SquareRootFloat(float number) {
    	
    		long i;
    		float x, y;
    		
    		const float f = 1.5F;
    		x = number *0.5f;
    		y  = number;
    		i  = * ( long * ) &y;
    		i  = 0x5f3759df - ( i >> 1 );
    		y  = * ( float * ) &i;
    		y  = y * ( f - ( x * y * y ) );
    		y  = y * ( f - ( x * y * y ) );
    		return number * y;
    	}
    	
    	int main()
    	{
    		float a; 
    	  clock_t start, finish;
    		double  duration;  
    		start = clock(); 
    		for(a=0 ; a<1000000; )
    		{
    			//printf("<--%f,-->%f\n",a,InvSqrt(a));
    			CoolSqrt(a);		
    			a += 0.1 ;
    		}	
    		finish = clock(); 
    		duration = (double)(finish - start) / CLOCKS_PER_SEC; 
    		printf( "%f seconds\n", duration ); 
    		getchar();
    		start = clock(); 
    		for(a=0 ; a<1000000; )
    		{
    			//printf("<--%f,-->%f\n",a,SquareRootFloat(a));
    			SquareRootFloat(a);		
    			a += 0.1 ;
    		}	
    		finish = clock(); 
    		duration = (double)(finish - start) / CLOCKS_PER_SEC; 
    		printf( "%f seconds\n", duration ); 
    		getchar();
    		start = clock(); 
    		for(a=0 ; a<1000000; )
    		{
    			//printf("<--%f,-->%f\n",a,sqrt(a));
    			sqrt(a);		
    			a += 0.1 ;
    		}	
    		finish = clock(); 
    		duration = (double)(finish - start) / CLOCKS_PER_SEC; 
    		printf( "%f seconds\n", duration ); 
    	}
    

    我的运行结果:在我工作的台式机上大约是标准库函数的1/3时间,在我的笔记本上是库函数的1/5时间!(PS,是笔记本上库函数运行时间增加了)。

    测试

    在某款嵌入式芯片上测试,时间稍有减小,虽然不是很多,但是它的对手可是库函数啊,每个字符都精校过的库函数啊!