学步园

http://haixiaoyang.wordpress.com/category/search-binary-search/

//Write a program to find the square root of a given numbe

//Binary search again.
double GetSquareRoot(double f, double exp)
{
	assert((f > 0.0 || abs(f) < exp) && exp > 0.0);

	double dbBeg = 0.0;
	double dbEnd = f;

	//Pitfall, miss 0.0<f<1.0 situation!! which square root is bigger
	//under this situation, the only difference is to identify the end.
	//You can't search a number beyond the scope right?
	while (dbEnd*dbEnd < f) //This is the ONLY difference!
		dbEnd *= 2.0;

	//Make a loop count, otherwise if exp is too small, the loop will be
	//dead loop because the precision NEVER reached!!! Pitfall
	int nCount = 100; 
	do 
	{
		double dbMid = (dbBeg + dbEnd)/2.0;
		double dbSqrDiff = dbMid*dbMid - f;
		if (abs(dbSqrDiff) < exp)
			break;
		if (dbSqrDiff < 0.0)
			dbBeg = dbMid;
		else 
			dbEnd = dbMid;
	} while (nCount-- >= 0);

	return (dbBeg + dbEnd)/2.0;
}

要考虑细致

可以用牛顿迭代法的思想实现

牛顿迭代是求极值

x = x - f'(x)/f''(x)

n^1/2 = x

x^2 - n = 0

如何尽快的找到x使得上式为0

x = x - (x^2-n)/2x = (x+n/x)/2

#include "stdafx.h"
#include <iostream> 
using namespace std;

double mysqrt(double a)
{
        double x=a;
        
        while(x*x-a>1e-6 || a-x*x>1e-6)
        {
                x=(x+a/x)/2;
        }
        
        return x;
}

int main(int argc, char* argv[])
{
        double a,x;
        cin>>a;
        x=mysqrt(a);
        cout<<x<<endl;
        return 0;
}