首页 > 代码库 > 一种快速开平方并取倒数算法

一种快速开平方并取倒数算法

       今天在查资料过程中,无意中看到这样一段神奇的代码,决定转载到自己的csdn博客,但是找了半天,愣是没找到csdn转载功能,此前经常看到别人转载文章,然后心里一直在想,是不是转载是一个隐藏功能,或者使用什么命令就可以了。于是特意谷歌了下,原来csdn的转载功能,根本没有什么快速转载、一键转载,只有对着原文复制、粘贴,然后在自己的博客里面重新排版,最后在发布文章时选择转载,这样该文章就成为一篇转摘的文章了。这么设计也有道理,只有不嫌麻烦的人,才会耐心的完成转载,算是提高了转载的门槛,避免出现大量重复文章。不过,这么设计的副作用就是,浪费了很多时间和精力。吐槽就到这里,还是看看这段神奇的快速开平方并取倒数代码:
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;
}
关于该段代码的更多说明,请参看这篇文章《0x5f3759df的数学原理》。
       下面为我编写的简单测试代码:
#include "stdafx.h"
#include <stdio.h>  
#include <stdlib.h>
#include <windows.h>
#include <math.h>

// 开平方取倒数
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;
}

int main()
{
	// 比较精度
	float val = 0.0f;
	val = 1.0f;
	printf("计算精度比较: \n");
	printf("输入值:   %f    快速算法: %f    VC函数: %f \n", val, InvSqrt(val), 1.0f / sqrt(val));

	val = 16.0f;
	printf("输入值:  %f    快速算法: %f    VC函数: %f \n", val, InvSqrt(val), 1.0f / sqrt(val));

	val = 25.0f;
	printf("输入值:  %f    快速算法: %f    VC函数: %f \n", val, InvSqrt(val), 1.0f / sqrt(val));

	val = 100.0f;
	printf("输入值: %f    快速算法: %f    VC函数: %f \n", val, InvSqrt(val), 1.0f / sqrt(val));

	printf("\n计算性能比较: \n");
	int count = 1000000;
	DWORD timeStart = 0, timeEnd = 0;
	timeStart = GetTickCount();
	for (int i = 0; i < count; i++)  
	{  
		val = InvSqrt(100.0f);  
	}  
	timeEnd  = GetTickCount();  
	printf("快速算法耗时: %f \n", (timeEnd - timeStart) * 0.001); 

	timeStart = GetTickCount();
	for (int i = 0; i < count; i++)  
	{  
		val = 1.0f / sqrt(100.0f);  
	}  
	timeEnd  = GetTickCount();  
	printf("VC函数耗时:   %f \n", (timeEnd - timeStart) * 0.001); 

	printf("\n");
	system("pause");
	return 0;
}
       这里与sqrt()分别比较了计算精度及计算性能,测试环境为vs2005,普通pc笔记本(其实是一台年久的、玩的了游戏、写得了代码的小黑)。从对比结果看,该快速算法在计算结果上有一点点误差,但是计算性能上很可观。下图为对比结果:

                               



一种快速开平方并取倒数算法