实现Math.sqrt

开发中有时候需要进行求根运算(比如判断整数是不是素数), 在Java中调用Math.sqrt()即可, 这个方法是怎么实现的呢?

整数的算数平方根

给定正整数 $c$ ,找出整数 $a$ ,使得 $a = \lfloor\sqrt{c} \rfloor$ ( $a$ 是所有平方 $\le {c}$ 的整数中最大的那个).

利用二分法的原理可以实现整数的求根运算,核心代码如下:

    public int sqrti(int a) {
        int i = 0;
        int j = a;
        while (i <= j) {
            int m = (i + j) / 2;
            int s = m * m;
            if (s == a) return m;
            else if (s > a) j = m - 1;
            else i = m + 1;
        }
        return j;
    }

上面的算法中 $j \le \sqrt{a} \le i$ . 在区间 $[0, a]$ 上不断猜想,直到条件不满足为止, 可以看出是以指数的速度收敛的.

有了整数的开方方法,实现浮点的开方就容易多了:

    public double sqrtd(double a) {
        double i = 0;
        double j = a;
        while (i != j) {
            double m = (i + j) / 2;
            double s = m * m;
            if (s == a) return m;
            else if (s > a) j = m;
            else i = m;
        }
        return j;
    }

对于实数 $a (a\ge 1)$ , $1 \le \sqrt{a} \le {a}$ 。对于实数 $a (0<a<1)$ , $a \le \sqrt{a} \le {1}$ , 所以 $\sqrt{a}$ 介于 $a$ 和 $1$ 之间。用这个结果可以对sqrtd的区间进行调整:

    public double sqrtd2(double a) {
        double i = 1;
        double j = a;
        while (i != j) {
            i = j;
            j = (j + a / j) / 2;
        }
        return j;
    }

sqrtd2实际上已经是属于迭代类型的方法。

牛顿迭代法

牛顿迭代法是数值分析中重要的方法. 很多方程不存在求根公式，因此求根的解析解非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要. 当精度达到一定程度时近似值和真实值在实际应用中并没有太大的差别, 因此数值解广泛应用与计算机和工程学中. 而牛顿迭代法正是提供了求解方程根的数值解.

牛顿迭代示意图

设 $f(x)$ 有足够好的性质, $r$ 是 $f(x)=0$ 的根,取 $x_n$ 作为 $r$ 的近似值,过 $(x_n, f(x_n))$ 作 $y=f(x)$ 的切线 $L$ , $L$ 交 $x$ 轴于 $(x_{n+1},0)$ 点, 有关系: $f'(x_n) = \frac{f(x_n)}{x_n - x_{n+1}}$ 得到迭代公式:
$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

牛顿迭代法实现sqrt

取 $f(x) = x^2-a (a>0)$ (满足迭代收敛条件,这里忽略), 则 $f(x)$ 的根也就是 $\sqrt{a}$ . 计算出迭代公式:
$f'(x) = 2x, \quad x_{n+1} = x_n - \frac{x_n^2-a}{2x_n} = \frac{1}{2}( x_n+\frac{a}{x_n} )$

    public double sqrtn(double a) {
        if (a < 0) return Double.NaN;
        if (a == 0) return 0;

        double e = 1e-10;
        double x;
        double y = a;
        do {
            x = y;
            y = (x + a / x) / 2;
        } while (Math.abs(x - y) > e);
        return x;
    }

牛顿迭代可以处理的类型远不止求根, 以计算机实现求三次根作为结束

    public double curt(double c) {
        double x;
        double y = 1;
        double e = 1e-10;

        do {
            x = y;
            y = (2 * x + c / (x * x)) / 3;
        } while (Math.abs(x - y) > e);
        return x;
    }

本文例子中大部分给的是核心代码, 并没有特别处理边界情况。

最后编辑于：2019.07.29 17:36:20