【C】库函数之sqrt

Compute square root

# include <math.h>

double sqrt(double x); 

   Value whose square root is computed.

   If the argument is negative, a domain error occurs.

  上述内容是C++官网对sqrt函数的介绍，可以看出sqrt函数用来求一个数字的平方根，并且该数字不能为负数，否则将会报错。

  接下来介绍两种实现sqrt函数的方法：

1、二分法

  既然sqrt函数是来求平方根的，不妨假设 x²=n ，从而将求平方根的过程转换为求解x的过程。将 x²=n 这个等式移项可以得到 x²-n=0 ，抽象化该等式，可以得到f(x)=x²-n=0，那么求解x的过程就转换成求解函数f(x)=x²-n与x轴的交点的横坐标的值。

   零点定理：若f(x)在(a,b)上连续，且f(a)*f(b)<0，则f(x)在(a,b)内至少有一个零点。

   不断地把函数f(x)的零点所在的区间一分为二，使得区间的两个端点逐步逼近零点，最后得到的零点的近似值就是x的值。

  算法思想：

a.首先使用二分法确定区间[left,right]，其中left=0,right=n;

b.然后计算出该区间的中间位置mid=(left+right)/2；

c.判断mid*mid是否大于n，如果大于，则缩小[left,right]的范围为之前的一半，反之，则继续缩小[left,right]的范围为之前的一半；

d.设置一个变量last存放每次比较结束后mid的值，不断重复c，直到last与mid的误差满足一定条件时，返回last的值即为x。

  注意：计算mid=(left+right)/2时，加法运算会溢出，由于数据类型为浮点型，因此不考虑移位运算，这里可以使用mid=left+(right-left)/2来代替。给出几种常见计算平均值的方法

    源代码：

/*
*	函数名称：MySqrt
*
*	函数功能：求一个数字的平方根(二分法)
*
*	入口参数：num
*
*	出口参数：ret
*
*	返回类型：double
*/

double MySqrt(double num)
{
	double left = 0.0;
	double right = num;
	double mid = 0.0;
	double last = 0.0;

	mid = left + (right - left) / 2.0;

	assert(num >= 0);
	
	while (fabs(last - mid) > EXP)
	{
		if ((mid * mid) > num)
		{
			right = mid;
		}
		else
		{
			left = mid;
		}

		last = mid;
		mid = left + (right - left) / 2.0;
	}

	return last;
}

2、牛顿迭代法

   首先x²=n的解可以转化为求函数f(x)=x²-n与x轴的交点的横坐标的值。在x轴上任选一点x0，过点（x0,f(x0)）作函数f(x)的切线交x轴于点x1，满足切线方程f(x0)=f'(x0)(x0-x1)，代入f(x)=x²-n中可以得到迭代表达式x1=(x0 + n/x0)/2。不断地求切线方程对应的迭代表达式，最终只要满足求出的结果在定义的精度范围内即可。

  源代码：

/*
*	函数名称：MySqrt
*
*	函数功能：求一个数字的平方根(牛顿迭代法)
*
*	入口参数：num
*
*	出口参数：ret
*
*	返回类型：double
*/

double MySqrt(double num)
{
	double last = 0.0;
	double ret = num;

	assert(num >= 0);

	do
	{
		last = ret;
		ret = (ret + num / ret) / 2;
	}while (fabs(last - ret) > EXP);

	return ret;
}

  主函数：

#define _CRT_SECURE_NO_WARNINGS 1

/*
* Copyright (c) 2018, code farmer from sust
* All rights reserved.
*
* 文件名称：Mysqrt.c
* 功能：求一个数字的平方根
*
* 当前版本：V1.0
* 作者：sustzc
* 完成日期：2018年4月3日19:09:38
*/

# include <stdio.h>
# include <math.h>
# include <assert.h>

# define EXP 0.00000000000000000000000001

int main(void)
{
	double n = 0.0;

	printf("请输入数字:");
	scanf("%lf", &n);
	printf("%lf的平方根是%lf\n", n, MySqrt(n));

	return 0;
}

  输出结果：