题解 | #求平方根#

本题可以使用牛顿迭代法来完成本题的求解，牛顿迭代法也是对 sqrt 的最佳实践。该算法来源于游戏 Quake 3 （雷神之锤3），大家感兴趣可以详细去了解一下，非常有意思。

引用 Wiki 对牛顿迭代法的两篇介绍：

Fast inverse square root

Newton's method

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        double res = 0;
        double temp = 0;
        temp = x / 2;
        int i = 0; // 计数器，避免过度迭代
        while (x >= 0 && i < 100) {
            i++;
            // 牛顿迭代公式
            res = temp - (temp * temp - x) / (2 * temp);
            double value = Math.abs(temp - res);
            // 用于控制精度
            if (value < 0.001) { 
                return (int)res; 
            } else {
                temp = res;
            }
        }
        return (int)x; 
    }
}