/**
 * 實現(xiàn)一個函數(shù), 完成 開根號 的操作, 方法簽名如下.
 * 
 * double sqrt(int v, double t)
 * <p>
 * 要求:
 * 
 * 不能調(diào)用系統(tǒng)庫函數(shù), 諸如 Math.sqrt(v) 之類的; 假設(shè)計算出的結(jié)果為 r, 要求滿足如下條件, , 其中 是真實的值, t 為給定的一個誤差范圍, 例如0.1等, 即你計算出的值要在給定的誤差范圍內(nèi). 實現(xiàn)語言不限,
 * 你條件可以比上述更加苛刻, 但不能寬松, 舉例而言, 我調(diào)用你的接口 sqrt(9, 0.21) 返回值屬于 [2.79, 3.21] 這個區(qū)間的任意一個都滿足條件.
 * </p>
 * 
 */
public class SqrtDemo {

    // 窮舉法
    private static double sqrt1(int v, double t) {
        double result = 0;
        Long start = new Date().getTime();

        while (true) {
            if ((result + t) * (result + t) >= Math.abs(v - t)) {
                Long end = new Date().getTime();
                System.out.println("自寫爆菊耗時：" + (end - start) + "ms");
                return result;
            }
            result += t;// 適當(dāng)分段
        }
    }

    // 二分法
    private static double sqrt2(int v, double t) {
        Long start = new Date().getTime();
        double value = v / 2;
        double low = 0, up = v;

        while (Math.abs(up - value * value) > t) {
            if (value * value > v) {
                low = 0;
                up = value;
            } else if (value * value < v) {
                low = value;
            }
            if (value == (low + up) / 2)
                break;
            value = (low + up) / 2;
        }
        Long end = new Date().getTime();
        System.out.println("自寫二分耗時：" + (end - start) + "ms");
        return value;
    }

    // !!牛頓快速迭代法
    // 求出根號a的近似值：首先隨便猜一個近似值x，然后不斷令x等于x和a/x的平均數(shù)，迭代個六七次后x的值就已經(jīng)相當(dāng)精確了戚啥。
    // 不斷用(x,f(x))的切線來逼近方程x^2-a=0的根年叮。根號a實際上就是x^2-a=0的一個正實根，這個函數(shù)的導(dǎo)數(shù)是2x纬纪。
    // 也就是說蚓再，函數(shù)上任一點(x,f(x))處的切線斜率是2x。那么包各，x-f(x)/(2x)就是一個比x更接近的近似值摘仅。
    // 代入f(x)=x^2-a得到x-(x^2-a)/(2x)，也就是(x+a/x)/2问畅。
    private static double sqrt3(int v, double t) {
        double result = 0, value = v;
        Long start = new Date().getTime();
        while (true) {
            result = value;
            value = (value + v / value) / 2;
            if (Math.abs(result - value) <= t) {
                Long end = new Date().getTime();
                System.out.println("自寫牛頓耗時：" + (end - start) + "ms");
                break;
            }
        }
        return result;
    }


    public static void main(String[] args) {
        System.out.println(sqrt1(1000000000, 0.00001));
        System.out.println(sqrt2(1000000000, 0.00000001));
        System.out.println(sqrt3(1000000000, 0.00000001));

        Long start = new Date().getTime();
        Math.sqrt(10000000);
        Long end = new Date().getTime();
        System.out.println("系統(tǒng)sqrt耗時：" + (start - end) + "ms");
        System.out.println(Math.sqrt(1000000000));
    }
}

自寫爆菊耗時：5530ms
31622.776601556234
自寫二分耗時：0ms
31622.776601683792
自寫牛頓耗時：0ms
31622.776601684047
系統(tǒng)sqrt耗時：0ms
31622.776601683792