java - 初始猜测的优化是否会使巴比伦方法快速找到平方根？

巴比伦的aka-Heron方法似乎是寻找n的平方根的快速算法之一。它的收敛速度取决于你最初猜测的距离。
现在，随着数字n的增加，根x的百分比减少。
根（10）：10-31%
10:100-10%
根部（100）：100-3%
根（1000）：1000-1%
基本上每个数字除以3。那就用它作为你的最初猜测。例如-

 public static double root(double n ) {
      //If number is 0 or negative return the number
            if(n<=0)
                return n ;
     //call to a method to find number of digits
            int num = numDigits(n)  ;
            double guess =  n ;
    //Divide by 0.3 for every digit from second digit onwards
            for (int i = 0 ; i < num-1 ; ++i )
                guess = guess * 0.3;
    //Repeat until it converges to within margin of error
            while (!(n-(guess*guess) <= 0.000001 && n-(guess*guess) >= 0 )) {
                double divide = n/guess ;
                guess = Math.abs(0.5*(divide+guess)) ;

            }

            return Math.abs(guess)  ;
        }

这是否有助于优化算法这是O（n）吗？

最佳答案

对。更有效的方法是利用浮点表示法，通过将二进制指数除以2，因为在浮点位上操作非常快。见Optimized low-accuracy approximation to `rootn(x, n)`。