easy-algorithm-interview-and-practice/mathcasebycase/用牛顿迭代求方根.md

1.前言

各种编程语言中都有实现求一个数方根的函数，即sqrt函数。但是，如果不用sqrt函数，只用四则运算让求一个数的方根，该怎么办勒？换句话说，让你自己实现sqrt函数，你能实现么？OK，各位最好先自己想想然后动手实现以下。如果遇到了困难，欢迎接着往下阅读本文。

2.用二分的思想

二分法是非常好用的套路。对于各种快速查找还有迭代类的运算都是一把好手。而且复杂度只有\log n。这里我们也可以采用类似的思路进行计算：假设一个start，一个end，假设最终方根值为result,初始值取n/2。然后根据result平方和与n的差的大小进行比较，更新start与end，最后求出结果。

直接上源码：

public class Root_Of_Num {

    public static double bin_sec_root(int n) {
        double start = 0;
        double end = n / 2.0;
        double result = n / 2.0;
        double eps = 0.00001; //精度

        double tmp = result * result - n;

        if (tmp < eps) {
            return result;
        }

        while (Math.abs(tmp) > eps) {
            if (tmp > 0) {
                end = result; //更新end 
                result = (start + result) / 2;
            } else {
                start = result; //更新start
                result = (result + end) / 2;
            }
            tmp = result * result - n;
        }

        return result;
    }
    
    public static void main(String[] args) {
        int n = 5;
        double result = bin_sec_root(n);
        System.out.println("result is: " + result);
    }
}

各位亲，是不是跟二分的思路很像？

3.用牛顿迭代

其实，更快的一种方式是用牛顿迭代的方法。关于牛顿迭代，以后会写专门的文章给大家介绍。先上代码：

public class Root_Of_Num {
    public static double newton_iteration_root(int n) {
        double result = 1.0; //迭代初始值
        double eps = 0.00001;
        double tmp = result*result - n;

        while(Math.abs(tmp) > eps) {
            //牛顿迭代公式
            result = 0.5 * (result + (n / result));
            tmp = result*result - n;
        }
        return result;
    }
    public static void main(String[] args) {
        int n = 5;
        double result = newton_iteration_root(n);
        System.out.println("result is: " + result);
    }
}

这里面最关键的一行其实就是迭代公式那行。要明白为什么这样迭代就能求出方根，需要有相应的数学知识作为基础。请同学们参考我有关牛顿迭代，泰勒展开的文章：http://blog.csdn.net/bitcarmanlee/article/details/52195617

牛顿迭代的速度也很快，一般迭代6-7次，就能得到精度相当高的结果！

最后不禁感叹，数学的力量是伟大的。一切的自然科学，都离不开数学的神奇魔力。只有数学好，才是真的好！