Category Archives: Algorithm

分布式一致性算法02：Multi-Paxos

Posted on by — No Comments ↓

分布式一致性算法02 Multi-Paxos算法

一、基本概念
Multi-Paxos算法，在Paxos的基础上，通过引入领导者（Leader）的概念，大幅提升了效率。

二、Multi-Paxos算法通常涉及三种角色：
Leader（领导者）/Proposer（提议者） ：在Multi-Paxos中，通常会选举出一个Leader作为Proposer，负责提出提议，并尝试让多数接受者接受该提议。
Acceptor（接受者） ：负责接受或拒绝提议者的提议。每个节点都可以是Acceptor，负责记录和确认提议。
Learner（学习者） ：负责学习最终达成一致的提议。

三、Multi-Paxos算法的基本过程
1、初始化阶段
首先，通过Paxos算法，选择一个领导者（Leader），它负责发起全部提议。

2、准备阶段（Prepare Phase）
领导者向集群中的其他节点发送Prepare消息，这些消息包含当前的最大提议编号。
Acceptor（接受者）接收到Prepare消息后，会返回一个响应，表明它们是否已经接收到更高编号的提议。
如果领导者接收到大多数节点的响应，表示它们没有更高的提议，则可以继续下一步。

3、接受阶段（Accept Phase）
领导者根据收到的Prepare响应选择一个提议编号，并向集群中的其他节点发送Accept消息。这些消息包含提议编号和提议值。
节点接收到Accept消息后，如果该提议编号高于它们当前已接受的提议，则会接受该提议并返回确认消息。如果大多数节点确认接受该提议，则该提议被接受。

4、提交阶段（Commit Phase）
一旦提议被大多数节点接受，领导者将该提议标记为已提交，并通知集群中的其他节点。
节点接收到提交通知后，将执行该提议，并更新其状态。

5、应用阶段（Apply Phase）
最后，领导者将已提交的提议应用到状态机中，并通知集群中的其他节点。
节点接收到应用通知后，也会将提议应用到其状态机中，从而确保所有节点的状态一致。

四、举例说明
假设我们有一个分布式系统，由10个节点组成：P1、P2是提议者（Proposer），A1、A2、A3、A4、A5是接受者（Acceptor），L1、L2、L3是学习者（Learner）。

1、初始化阶段
在Multi-Paxos中，任何提议者都可以被选为领导者。
系统启动时，通过某种机制（比如Paxos算法）选举出一个新的领导者，这里假设P1被选为领导者。

2、准备阶段（Prepare Phase）
领导者P1，生成一个提议编号（例如7），向所有接受者询问，是否可以接受编号为7的提议。
接受者A1~A5收到消息后，由于提议编号7大于它们之前见过的任何提议编号，将进入承诺状态，并向P1发送可接受提议编号7的提议，并承诺不会接受任何编号小于7的提议。
【通过算法优化，其实可以节省提议编号这个阶段，直接发起提议】

3、接受阶段（Accept Phase）
当受到大多数接受者同意提议编号的消息后，P1向集群中的所有接受者发送Accept消息，提议编号7的内容为V7。
接收者收提议后，如果该提议编号高于它们当前已接受的提议，则会接受该提议并返回确认消息。

4、提交阶段（Commit Phase）
一旦P1收到来自多数接受者的已接受消息，它将向所有接受者发送提交消息，指示它们可以提交这个提议。

5、应用阶段（Apply Phase）
接受者在收到提交消息后，将提议的键值对应用到状态机中，并将结果通知学习者。

五、与Paxos算法对比
并发性：Paxos算法在每次达成共识时都需要进行两轮消息传递，这限制了它的并发能力。而Multi-Paxos通过引入领导者（Leader）的概念，允许多个提议者并发地提出提议，从而提高了并发性。
消息复杂度：在Paxos算法中，每个提议都需要两轮的通信（Prepare和Accept阶段），这增加了消息的复杂度。Multi-Paxos通过减少通信轮次，允许领导者在一轮中提出多个提议，从而减少了消息的复杂度。
实时性：由于Multi-Paxos允许并发提议，它在实时性方面通常优于Paxos算法。在Paxos算法中，每个提议都需要等待前一个提议完成后才能开始，这可能导致延迟。
容错性：Paxos算法和Multi-Paxos都具有很好的容错性，但Multi-Paxos由于其并发性，在某些容错情况下可能表现更好，例如在领导者失败时可以快速选举新领导者并继续处理提议。
实现复杂度：Paxos算法的实现相对复杂，而Multi-Paxos虽然在理论上提供了并发性的优势，但其实现也引入了额外的复杂性，如领导者选举和故障恢复机制。
优化和变种：Multi-Paxos有许多优化和变种，如Fast Paxos和EPaxos，它们通过进一步减少通信轮次或利用特定的系统特性来提高性能。而在实际应用中，许多系统采用Multi-Paxos或其变种，如Raft算法，以提高性能。

分布式一致性算法01：Paxos

Posted on by — No Comments ↓

分布式一致性算法01 Paxos算法

一、基本概念
Paxos是分布式一致性的经典算法，由Leslie Lamport在1990年提出。

二、Paxos算法通常涉及三种角色：
Proposer（提议者） ：负责提出提议（Proposal），即向系统中提出一个值。Proposer通常是客户端，负责发起提议并分配一个不重复的自增ID给每个提议。
Acceptor（接受者） ：参与决策过程，负责接收并回应Proposer的提议。每个Acceptor只能接受一个值，并且为了保证最多只有一个值被选定（Chosen），Proposal必须被超过一半的Acceptors所接受。
Learner（学习者） ：负责学习最终被选定的值。Learner不参与协商过程，只是接收并记录最终被选定的值。
在实际过程中，一个节点可以同时承担1~3个角色。

三、Paxos算法的基本过程
1、准备阶段（Prepare Phase）：
提议者（Proposer）选择一个提议编号（ballot number），并将其发送给所有接受者（Acceptor）。
接受者在接收到提议者的准备请求后，如果当前编号大于其已承诺的最高编号，则更新其承诺编号，并返回一个承诺（promise）给提议者，承诺中包含当前已接受的最高编号和值。

2、提议阶段（Proposal Phase）：
提议者收集到多数接受者的承诺后，选择一个值（value），并结合最新的提议编号，生成提议（propose）消息发送给接受者。
接受者在接收到提议消息后，如果提议编号大于其已有的承诺编号，则接受该提议，并返回确认消息给提议者。

3、决定阶段（Decide Phase）：
提议者收集到多数接受者的确认消息后，可以决定该值为最终值，并将其写入日志或状态机中。
学习者（Learner）从提议者处获取并学习最终决定的值，确保所有节点都有一致的状态。

四、举例说明：
假设我们有一个分布式系统，包含10个节点：P1、P2是提议者，A1、A2、A3、A4、A5是接受者，L1、L2、L3是学习者。

1、准备阶段：
P1提出一个提议编号，编号为1。
P1向所有接受者A1~A5发送询问，询问P1将发起编号为1提议是否可以。
A1收到提议时，并没有反馈过任何一次提议，于是反馈可以接受，并承诺，后续不会接受编号比1小的提议。A2~A4类似。

几乎同时，P2提出一个提议，编号为5。
P2向所有接受者A1~A5发送询问，询问P2将发起编号为5提议是否可以。
A1收到提议时，承诺的最小编号为1，于是反馈可以接受，并承诺，后续不会接受编号比5小的提议。A2~A4类似。

到这里，P1和P2的提议，前后都被允许提交了。当然，也有情况可能是，部分节点先收到了P2，这种情况下，P1的提议编号就无效了，需要重新拟定编号，这个编号必须单调增加。

2、提议阶段
P1收到了过半节点的提议编号反馈，向所有接受者A1~A5发送提议，告知提议编号为1的提议值为V1。
接受者收到提交消息时，已经无法接收比5小的提议，于是就拒绝P1，提议不通过。

P2收到了过半节点的提议编号反馈，向所有接受者A1~A5发送提议，告知提议编号为5的提议值为V5。
接受者收到提交消息时，反馈P2同意了5号提议。

3、决定阶段
当提议5收到过半同意反馈时（5个节点中3个以上同意），认为提议通过，各节点并将V5写入日志。
此时，学习者L1、L2、L3也会学习到V5的结果，并写入日志。

五、Paxos算法的特点
多数同意：在Paxos算法中，只有当提议者收到超过半数接受者的同意时，提议才可能被提交。
唯一性：Paxos算法保证了在任何给定的一轮中，只有一个提议可以被接受。
容错性：即使在一些节点失败的情况下，Paxos算法也能够工作。
Paxos算法的实现和理解都相当复杂，但它是许多现代分布式系统一致性协议的基础，如Raft算法等。

编译guetzli

Posted on by — No Comments ↓ 
#1.下载并安装配置vcpkg
git clone https://github.com/microsoft/vcpkg.git
cd vcpkg
bootstrap-vcpkg.bat
vcpkg integrate install
vcpkg install libpng

# 如果用CMake，记录下面的输出路径
CMake projects should use:
"-DCMAKE_TOOLCHAIN_FILE=D:/Build/vcpkg/scripts/buildsystems/vcpkg.cmake"

#2.下载guetzli
git clone https://github.com/google/guetzli.git

#3.用VS2017进行编译

#4.测试效果
整体上压缩比率还是很不错的，但这个压缩速度，还是放弃吧。

Update:
如果是图像压缩的话，现在webp格式还是很不错的，可以直接下载工具：
https://developers.google.com/speed/webp/download
https://chromium.googlesource.com/webm/libwebp/

运煤问题

Posted on by — No Comments ↓

提问：
一个山西煤老板，在矿区开采了3000吨煤需要运送到市场上去卖，从矿区到市场有1000公里。现在有一列烧煤的火车，该火车最多只能装1000吨煤，但其每一公里需要耗一吨煤作为燃料。请问，怎么运送才能运最多的煤到集市？（火车可以调头，火车最终不需要返回煤矿）

约束：
1、火车一定需要调头
2、调头的原则是，消耗的燃料越少越好
3、当煤不足一车时，仍然要当作一车运输

解答：
1、当煤多于2000吨时，火车一定要运三次，同样的路要跑五次
1000吨煤，走五次，可以走1/5路程
2、当煤多余1000吨时，火车一定要运两次，同样的路要跑三次
1000吨煤，走三次，可以走1/3路程
3、最终剩余1000吨时，直接跑到终点
最后剩余路程为1-1/5-1/3=7/15
跑完后剩余的煤为1000-7/15*1000=1000*8/15=533零1/3吨

以上。

二进制数字中1的个数

Posted on by — No Comments ↓ 
#include "stdafx.h"
#include <nmmintrin.h>

/*
 *通过移位计算1的个数
 *每一位都要判断和处理
 */
int BitCount(unsigned int n)
{
	unsigned int c = 0;
	while (n >0)
	{
		if ((n & 1) == 1)++c;
		n >>= 1;
	}
	return c;
}

/*
 *通过减法及位运算，保证每次至少消除一个1
 *只处理1的位，0的位不处理
 */
int BitCountWithMinus(unsigned int n)
{
	unsigned int c = 0;
	for (c = 0; n; ++c)
	{
		n &= (n - 1);
	}
	return c;
}

/*
*将32位数字，截为4个8位数
*通过查表，得到每个8位数中1的个数，然后求和
*/
int BitCountLUT8(unsigned int n)
{
	unsigned char BitsSetTable256[256] = { 0 };

	for (int i = 0; i <256; i++)
	{
		BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
	}

	unsigned int c = 0;

	unsigned char* p = (unsigned char*)&n;

	c = BitsSetTable256[p[0]] +
		BitsSetTable256[p[1]] +
		BitsSetTable256[p[2]] +
		BitsSetTable256[p[3]];

	return c;
}

/*
*将32位数字，截为4个8位数
*通过查表，得到每个8位数中1的个数，然后求和
*LUT表已经计算好
*/
int BitCountLUT8Static(unsigned int n)
{
	unsigned int table[256] =
	{
		0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
	};

	return table[n & 0xff] +
		table[(n >> 8) & 0xff] +
		table[(n >> 16) & 0xff] +
		table[(n >> 24) & 0xff];
}

/*
*将32位数字，截为8个4位数
*通过查表，得到每个4位数中1的个数，然后求和
*LUT表已经计算好
*/
int BitCountLUT4Static(unsigned int n)
{
	unsigned int table[16] =
	{
		0, 1, 1, 2,
		1, 2, 2, 3,
		1, 2, 2, 3,
		2, 3, 3, 4
	};

	unsigned int count = 0;
	while (n)
	{
		count += table[n & 0xf];
		n >>= 4;
	}
	return count;
}

/*
*将32位数字，相邻的2位求和，然后相邻的4位求和
*然后相邻的8位、16位、32位求和
*/
int BitCountParallel(unsigned int n)
{
	n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
	n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
	n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
	n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
	n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);

	return n;
}

/*
*第一行，计算每三位的1的个数（其实11*3是33位，但最高一位可以假设为0，所以没问题）
*第二行，实际上是先计算了相邻6位中1的个数（不会产生进位，结果最多占到3位），并将前三位置为0
*然后通过取模，相当于将每6位数字做了加法
*/
int BitCountMagic(unsigned int n)
{
	unsigned int tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
	return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}

unsigned int n = 127;
unsigned int bitCount = _mm_popcnt_u32(n);


/*
*将8位数字，转换为MY_UNSIGHED_CHAR结构体，然后求和
*/
struct MY_UNSIGHED_CHAR
{
	unsigned a : 1;
	unsigned b : 1;
	unsigned c : 1;
	unsigned d : 1;
	unsigned e : 1;
	unsigned f : 1;
	unsigned g : 1;
	unsigned h : 1;
};

long BitCountStuct(unsigned char b)
{
	struct MY_UNSIGHED_CHAR *by = (struct MY_UNSIGHED_CHAR*)&b;
	return (by->a + by->b + by->c + by->d + by->e + by->f + by->g + by->h);
}

int _tmain(int argc, _TCHAR* argv[])
{
	printf("There are %d 1 in 133\n", BitCount(133));
	printf("There are %d 1 in 133\n", BitCountWithMinus(133));
	printf("There are %d 1 in 133\n", BitCountLUT8(133));
	printf("There are %d 1 in 133\n", BitCountLUT8Static(133));
	printf("There are %d 1 in 133\n", BitCountLUT4Static(133));
	printf("There are %d 1 in 133\n", BitCountParallel(133));
	printf("There are %d 1 in 133\n", BitCountMagic(133));
	printf("There are %d 1 in 133\n", BitCountStuct(133));
	return 0;
}

用位运算实现加减乘除

Posted on by — No Comments ↓ 
        //加法
	public static int add(int a, int b)  
	{  
	    int ans;  
	    while(b!=0)  
	    {
	        ans = a^b;
	        b = ((a&b)<<1);
	        a = ans;  
	    }  
	    return a;  
	}  
	
	//减法
	public static int sub(int a, int b)
	{  
	    return add(a, -b);  
	}
	
	//正数乘法
	private static int posMultiply(int a,int b)  
	{  
	    int ans = 0;  
	    while(b>0)  
	    {  
	        if((b&0x1)==1)ans = add(ans, a);  
	        a = (a<<1);  
	        b = (b>>1);  
	    }  
	    return ans;  
	}  
	  
	//乘法
	public static int multiply(int a,int b)  
	{  
	    if(a==0||b==0)return 0;  
	    if(a>0 && b>0)  
	        return posMultiply(a, b);  
	    if(a<0)  
	    {  
	        if(b<0)  
	        {  
	            return posMultiply(-a, -b);  
	        } 
	        else
	        {
	        	return -posMultiply(-a, b ); 
	        }
	    }
	    else
	    {
	    	return -posMultiply(a, -b);
	    }
	}  
	  
	//正数除法
	private static int posDiv(int x,int y)  
	{  
	    int ans=0;  
	    for(int i=31;i>=0;i--)  
	    {
	        if((x>>i)>=y)  
	        {  
	            ans+=(1<<i);  
	            x-=(y<<i);  
	        }  
	    }  
	    return ans;  
	}  
	  
	//除法
	public static int div( int a, int b )  
	{
		assert(b!=0);
	    if(a==0)return 0;

	    if(a>0)  
	    {  
	        if(b>0)
	        {
	            return posDiv(a,b); 
	        }
	        else
	        {
	        	return -posDiv( a,-b);  
	        }
	    }  
	    else
	    {
	    	if(b>0)
	    	{
		        return -posDiv(a, b);  
	    	}
	    	else
	    	{
	    		return -posDiv(-a, -b);  
	    	}
	    }
	    
	}   
	
	//求负数
	public static int negtive(int a)
	{  
	    return add(~a, 1);  
	}
	  
	//比较正数大小
	private static boolean isbigerPos( int a, int b )   
	{
	    int c = 1;  
	    b = (a^b);  
	    if(b==0)return false;
	    
	    while(b>0)  
	    {  
	    	b>>=1;
	        c <<= 1;  
	    }  
	    return (c&a)==0;  
	}   
	  
	//比较大小   
	public static boolean isbiger( int a, int b )   
	{
	    if(a<0)  
	    {  
	        if(b<0)  
	        {  
	            return isbigerPos( negtive(b), negtive(a) );  
	        }
	        else
	        {
	        	return false;  
	        }
	    }
	    else
	    {
		    if(b<0)
		    {
		        return true;  
		    }
		    else
		    {
		    	return isbigerPos(a, b);  
		    }
	    }

	}

	public static int divideby3(int x)  
	{  
	    int sum = 0;  
	    while(x > 3)  
	    {  
	        sum = add(x>>2 , sum);  
	        x = add(x>>2 , x&3);  
	    } 
	    if(x == 3) 
	    {
	        sum = add(sum , 1);
	    }
	    return sum;  
	}  
	
	public static void main(String[] args)
	{
		System.out.println(add(13,19));
		System.out.println(sub(13,19));
		System.out.println(multiply(13,19));
		System.out.println(div(10,5));
		System.out.println(negtive(13));
		System.out.println(isbiger(10,5));
		System.out.println(isbiger(10,11));
		
		System.out.println(divideby3(15));
		System.out.println(divideby3(14));
		System.out.println(divideby3(13));
		System.out.println(divideby3(12));
		System.out.println(divideby3(11));
	}

几种常见求解平方根的方法

Posted on by — No Comments ↓ 
        //精度
	private final static double accuracy= 1e-6;

	/**
	 * 暴力求解
	 */
	public static double bruteSqrt(double x)
	{
		assert(x>=0);
		double ans=0.0;
		while (Math.abs(x - ans * ans) > accuracy)ans += accuracy;
		return ans;
	}

	/**
	 * 牛顿法求解
	 */
	public static double newtonSqrt(double x)
	{
		assert(x>=0);
		double avg = x;
		double last_avg = Double.MAX_VALUE;

		while (Math.abs(avg - last_avg) > accuracy)
		{
			last_avg = avg;
			avg = (avg + x / avg) / 2;
		}
		return avg;
	}

	/**
	 * 二分法求解
	 */
	public static double binarySqrt(double x)
	{
		assert(x>=0);

		double low = 0;
		double high = x;
		double mid = Double.MAX_VALUE;
		double last_mid = Double.MIN_VALUE;

		while (Math.abs(mid - last_mid) > accuracy)
		{
			last_mid = mid;
			mid = (low + high)/2;
			if (mid*mid>x)high = mid;
			if (mid*mid<x)low = mid;
		}
		return mid;

	}

	private final static int[] LUT =
	{ 0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53, 55, 57, 59, 61, 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83, 84,
			86, 87, 89, 90, 91, 93, 94, 96, 97, 98, 99, 101, 102, 103, 104, 106, 107, 108, 109, 110, 112, 113, 114, 115,
			116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 128, 128, 129, 130, 131, 132, 133, 134, 135, 136,
			137, 138, 139, 140, 141, 142, 143, 144, 144, 145, 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155,
			155, 156, 157, 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168, 169, 170, 170, 171,
			172, 173, 173, 174, 175, 176, 176, 177, 178, 178, 179, 180, 181, 181, 182, 183, 183, 184, 185, 185, 186,
			187, 187, 188, 189, 189, 190, 191, 192, 192, 193, 193, 194, 195, 195, 196, 197, 197, 198, 199, 199, 200,
			201, 201, 202, 203, 203, 204, 204, 205, 206, 206, 207, 208, 208, 209, 209, 210, 211, 211, 212, 212, 213,
			214, 214, 215, 215, 216, 217, 217, 218, 218, 219, 219, 220, 221, 221, 222, 222, 223, 224, 224, 225, 225,
			226, 226, 227, 227, 228, 229, 229, 230, 230, 231, 231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237,
			237, 238, 238, 239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246, 246, 247, 247, 248,
			248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255 };

	/**
	 * 查表法求解
	 */
	public static int intLutSqrt(int x)
	{
		int xn;

		if (x >= 0x10000)
		{
			if (x >= 0x1000000)
			{
				if (x >= 0x10000000)
				{
					if (x >= 0x40000000)
					{
						xn = LUT[x >> 24] << 8;
					}
					else
					{
						xn = LUT[x >> 22] << 7;
					}
				}
				else
				{
					if (x >= 0x4000000)
					{
						xn = LUT[x >> 20] << 6;
					}
					else
					{
						xn = LUT[x >> 18] << 5;
					}
				}

				xn = (xn + 1 + (x / xn)) >> 1;
				xn = (xn + 1 + (x / xn)) >> 1;
				return ((xn * xn) > x) ? --xn : xn;
			}
			else
			{
				if (x >= 0x100000)
				{
					if (x >= 0x400000)
					{
						xn = LUT[x >> 16] << 4;
					}
					else
					{
						xn = LUT[x >> 14] << 3;
					}
				}
				else
				{
					if (x >= 0x40000)
					{
						xn = LUT[x >> 12] << 2;
					}
					else
					{
						xn = LUT[x >> 10] << 1;
					}
				}

				xn = (xn + 1 + (x / xn)) >> 1;

				return ((xn * xn) > x) ? --xn : xn;
			}
		}
		else
		{
			if (x >= 0x100)
			{
				if (x >= 0x1000)
				{
					if (x >= 0x4000)
					{
						xn = (LUT[x >> 8]) + 1;
					}
					else
					{
						xn = (LUT[x >> 6] >> 1) + 1;
					}
				}
				else
				{
					if (x >= 0x400)
					{
						xn = (LUT[x >> 4] >> 2) + 1;
					}
					else
					{
						xn = (LUT[x >> 2] >> 3) + 1;
					}
				}

				return ((xn * xn) > x) ? --xn : xn;
			}
			else
			{
				if (x >= 0)
				{
					return LUT[x] >> 4;
				}
			}
		}

		return -1;
	}

	/**
	 * Quake III中快速求解平方根倒数的方法
	 */
	public static float fastInvSqrt(float x)  
	{  
	     float xhalf = 0.5f*x;  
	     int f2i = Float.floatToRawIntBits(x);
	     f2i = 0x5f375a86-(f2i>>1);
	     x = Float.intBitsToFloat(f2i);
	     x = x*(1.5f-xhalf*x*x);
	     x = x*(1.5f-xhalf*x*x);
	     return x;  
	}
	
	/**
	 * Quake III中快速求解平方根方法
	 */
	public static float fastSqrt(float x) {  
	    float y=x;
	    float xhalf = 0.5f*x;
	    int f2i = Float.floatToRawIntBits(x);  
	    f2i = 0x5f3759df-(f2i>>1);  
	    x = Float.intBitsToFloat(f2i);  
	    x  = x * (1.5f-(xhalf*x*x));  
	    x  = x * (1.5f-(xhalf*x*x));  
	    return y*x;  
	}

	public static void main(String[] args)
	{
		System.out.println(bruteSqrt(3));
		System.out.println(newtonSqrt(3));
		System.out.println(binarySqrt(3));
		System.out.println(intLutSqrt(64));
		System.out.println(1/fastInvSqrt(3));
		System.out.println(fastSqrt(3));
	}